城市交通
题目描述
有n个城市，编号1~n，有些城市之间有路相连，有些则没有，有路则当然有一个距离。现在规定只能从编号小的城市走到编号大的城市，问你从编号为1的城市走到编号为n的城市要花费的最短距离是多少？
输入
输入格式：
先输入一个n，表示城市数，n<100。
下面的n行，是一个n*n的邻接矩阵map[1..n,1..n]。
map[i,j]=0，表示城市i和城市j之间没有路相连，否则为两者之间的距离。
输出
输出格式：
一个数，表示从城市1走到城市n的最短距离。
输入数据保证可以从城市1走到城市n。
样例输入
6 0 1 4 1 0 0 1 0 2 0 4 0 4 2 0 0 0 3 1 0 0 0 3 2 0 4 0 3 0 2 0 0 3 2 2 0
样例输出
3
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include<iostream> using namespace std; int main() { int n,i,j,k; cin>>n; int a[n+1][n+1]; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { cin>>a[i][j]; if(a[i][j]==0) {a[i][j]=9999; } } } for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(a[i][j]>a[i][k]+a[k][j]) a[i][j]=a[i][k]+a[k][j]; cout<<a[1][n]; } |
Subscribe
计数器 9794031
OI 课件=>
OI 课件=>