校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
本题目包含多组数据,请处理到文件结束。
对于每组数据,请在一行里输出最短需要行走的距离。如果不存在从S到T的路线,就输出-1.
3 3
2 <>
每组数据第一行包含两个正整数N和M(0Output
Sample Input
0 1 1
0 2 3
1 2 1
0 2
3 1
0 1 1
1 2
Sample Output
-1
代码
#include
Comments | NOTHING