校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;
	}
}