描述

罗老师被邀请参加一个舞会，是在城市n，而罗老师当前所处的城市为1,附近还有很多城市2~n-1，有些城市之间没有直接相连的路，有些城市之间有直接相连的路，这些路都是双向的，当然也可能有多条。

现在给出直接相邻城市的路长度，罗老师想知道从城市1到城市n，最短多少距离。

格式

输入格式

输入n, m，表示n个城市和m条路;

接下来m行，每行a b c， 表示城市a与城市b有长度为c的路。

输出格式

输出1到n的最短路。如果1到达不了n，就输出-1。

样例

输入样例

5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100

输出样例

90

限制

时间限制：1000 ms
内存限制：65536 KB

代码

  1. #include<stdio.h>
  2. int a[200][200],b[200][200],path[200][200];
  4. void floyd(int n)
  5. {
  6.     int i,j,k;
  7.     for(i=1; i<=n; i++)
  8.     {
  9.         for(j=1; j<=n; j++)
  10.         {
  11.             if(i!=j)
  12.                 path[i][j]=i;
  13.             else
  14.                 path[i][j]=-1;
  15.         }
  16.     }
  17.     for(k=1; k<=n; k++)
  18.     {
  19.         for(i=1; i<=n; i++)
  20.         {
  21.             for(j=1; j<=n; j++)
  22.             {
  23.                 if(a[i][j]>a[i][k]+a[k][j])
  24.                 {
  25.                     a[i][j]=a[i][k]+a[k][j];
  26.                     path[i][j]=path[k][j];
  27.                 }
  28.             }
  29.         }
  30.     }
  31. }
  33. int main()
  34. {
  35.     int n,m,i,j;
  36.     scanf("%d %d",&n,&m);
  37.     for(i=1; i<=m; i++)
  38.     {
  39.         int x,y,z;
  40.         scanf("%d %d",&x,&y);
  41.         if(b[x][y]==0)
  42.             scanf(" %d",&a[x][y]);
  43.         else
  44.         {
  45.             scanf(" %d",&z);
  46.             if(z<a[x][y])
  47.                 a[x][y]==z;
  48.         }
  49.         b[x][y]=1;
  50.     }
  51.     for(i=1;i<=m;i++)
  52.     {
  53.         for(j=1;j<=m;j++)
  54.         {
  55.             if(a[i][j]==0)
  56.             a[i][j]=999;
  57.         }
  58.     }
  59.     floyd(n);
  60.     if(a[1][n]==999)
  61.         printf("-1");
  62.     else
  63.         printf("%d",a[1][n]);
  64.     return 0;
  65. }