Floyd算法应用

发布于 2018-04-22  963 次阅读


校OJ P1008雾霾大作战

雾霾大作战

Description

京津冀地区常发生雾霾,厦门人普遍感受不深。如今厦门有时也会发生雾霾,厦门市政府决定推行公共自行车来解决雾霾问题。
政府决定在厦禾路上设置了N 个自行车出租站1,2,…,N。市民可在这些自行车出租站租用自行车,并在下面的任何一个自行车出租站归还自行车。自行车出租站i 到自行车出租站j 之间的租金为r[i,j],表示第i个站点到第j个站点的租金。试设计一个算法,计算出从自行车出租站1 到自行车出租站N 所需的最少租金。

Input

测试数据的第一行是一个整数N( 1 <= N <= 50 )表示该测试数据共有N个自行车出租站。接下来的N-1 行是r[i,j] ( 1 <= i < j <= N ),( 1 <= r[i,j] <= 1000 ),第N行有N-1个数字。

Output

所需的最少租金。

Sample Input

3
5 15
7

Sample Output

12

Hint

输入
3(3个自行车出租站)
5(出租站1到出租站2的租金) 15(出租站1到出租站3的租金)
7(出租站2到出租站3的租金)
输出:
12(最少租金5+7=12)

思路

看代码注释(第二题和第一题差不多)

代码

#include 
#include 

using namespace std;

int map[51][51];

int main(){
	int n;	
	scanf("%d", &n);
	for(int i = 0; i < n; i++) // 初始化化01矩阵,i-j的距离
		for(int j = 0; j < n; j++)
			if(i == j) map[i][j] = 0;
			else map[i][j] = 1e9; // 到不了表示无穷大
	for(int i = 0; i < n-1; i++){
		for(int j = i; j < n-1; j++){
			int money;
			scanf("%d", &money);
			map[i][j+1] = min(map[i][j+1], money); // 表示i - (j+1)要花的钱
			map[j+1][i] = min(map[j+1][i], money); // 表示(j+1) - i要花的钱
		}
	}
	int s = 0, e = n-1; // 从初始位置到最后一个点
        //Floyd算法核心
	for(int k = 0; k < n; k++)
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				map[i][j] = min(map[i][j], map[i][k] + map[k][j]); // 用dp来求最小钱
	cout << map[s][e] << endl;
}

HDOJ P1874畅通工程续

畅通工程续

Problem Description

某省自从实行了很多年的畅通工程计划后,终于修建了很多路。不过路多了也不好,每次要从一个城镇到另一个城镇时,都有许多种道路方案可以选择,而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。
现在,已知起点和终点,请你计算出要从起点到终点,最短需要行走多少距离。

Input

本题目包含多组数据,请处理到文件结束。
每组数据第一行包含两个正整数N和M(0

Output

对于每组数据,请在一行里输出最短需要行走的距离。如果不存在从S到T的路线,就输出-1.

Sample Input

3 3
0 1 1
0 2 3
1 2 1
0 2
3 1
0 1 1
1 2

Sample Output

2
-1

<>

代码

#include 
#include 

using namespace std;

int map[201][201];

int main(){
	int n, m;	
	while(scanf("%d %d", &n, &m) != EOF){
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				if(i == j) map[i][j] = 0;
				else map[i][j] = 1e9;
		for(int i = 0; i < m; i++){
			int x, y, z;
			scanf("%d %d %d", &x, &y, &z);
			map[x][y] = min(map[x][y], z);
			map[y][x] = min(map[y][x], z);
		}
		int s, e;
		scanf("%d %d", &s, &e);
		for(int k = 0; k < n; k++)
			for(int i = 0; i < n; i++)
				for(int j = 0; j < n; j++)
					map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
		if(map[s][e] == 1e9)
			cout << -1 << endl;
		else
			cout << map[s][e] << endl;
	}
}