题目描述
NowCoder 今年买了一辆新车, 他决定自己开车回家过年. 回家过程中要经过 n 个大小收费站, 每个收费站的费用不同, 你能帮他计算一下最少需要给多少过路费吗?
输入描述:
输入包含多组数据, 每组数据第一行包含两个正整数 m(1≤m≤500) 和 n(1≤n≤30), 其中 n 表示有 n 个收费站, 编号依次为 1,2,...,n. 出发地的编号为 0, 终点的编号为 n, 即需要从 0 到 n.
紧接着 m 行, 每行包含三个整数 f,t,c,(0≤f, t≤n; 1≤c≤10), 分别表示从编号为 f 的地方开到 t, 需要交 c 元的过路费.
输出描述:
对应每组数据, 请输出至少需要交多少过路费.
输入
- 8 4
- 0 1 10
- 0 2 5
- 1 2 2
- 1 3 1
- 2 1 3
- 2 3 9
- 2 4 2
- 3 4 4
输出
- 7
- #include "stdio.h"
- int main(){
- int a[31][31];
- int m,n;
- while(scanf("%d%d",&m,&n)!=EOF){
- for(int i=0;i<31;i++){
- for(int j=0;j<31;j++){
- a[i][j]=0;
- }
- }
- int f,t,c;
- for(int i=0;i<m;i++){
- scanf("%d%d%d",&f,&t,&c);
- a[f][t]=c;
- }
- for(int k=0;k<=n;k++){
- for(int i=0;i<=n;i++){
- for(int j=0;j<=n;j++){
- if(k!=i&&k!=j&&i!=j){
- if(a[i][k]>0&&a[k][j]>0&&a[i][j]>0)
- a[i][j]=(a[i][k]+a[k][j])<a[i][j]?a[i][k]+a[k][j]:a[i][j];
- else if(a[i][k]>0&&a[k][j]>0&&a[i][j]==0)
- a[i][j]=a[i][k]+a[k][j];
- }
- }
- }
- }
- printf("%d\n",a[0][n]);
- }
- }