城市交通
Time Limit:1000MS——Memory Limit:65536K
题目描述
有n个城市，编号1~n，有些城市之间有路相连，有些则没有，有路则当然有一个距离。现在规定只能从编号小的城市到编号大的城市，问你从编号为1的城市到编号为n的城市之间的最短距离是多少？
输入
先输入一个n，表示城市数，n小于100。
下面的n行是一个n*n的邻接矩阵map[i,j],其中map[i,j]=0表示城市i和城市j之间没有路相连，否则为两者之间的距离。
输出
输出格式：一个数，表示最少要多少时间。
输入数据保证可以从城市1飞到城市n。
样例输入
11
0 5 3 0 0 0 0 0 0 0 0
5 0 0 1 6 3 0 0 0 0 0
3 0 0 0 8 0 4 0 0 0 0
0 1 0 0 0 0 0 5 6 0 0
0 6 8 0 0 0 0 5 0 0 0
0 3 0 0 0 0 0 0 0 8 0
0 0 4 0 0 0 0 0 0 3 0
0 0 0 5 5 0 0 0 0 0 3
0 0 0 6 0 0 0 0 0 0 4
0 0 0 0 0 8 3 0 0 0 3
0 0 0 0 0 0 0 3 4 3 0
样例输出
13
解题思路
如果可以走的话，就选择走或者不走。注意min函数不要打错（血的教训 ）
AC完整程序
#include<stdio.h>
int min(int a,int b){
return a<b?a:b;
}
int main(){
int n,t,sum[100]={0};
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&t);
if(t>0){
if(sum[j]>0){
sum[j]=min(t+sum[i],sum[j]);
}
else sum[j]=t+sum[i];
}
}
}
printf("%d",sum[n]);
return 0;
}