九度题目1447：最短路

题目1447：最短路
时间限制：1 秒
内存限制：128 兆
特殊判题：否
提交：1650
解决：798
题目描述：
在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？

输入：
输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。输入保证至少存在1条商店到赛场的路线。
当输入为两个0时，输入结束。

输出：
对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间。

样例输入：
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0样例输出：
3
2

迪杰斯特拉小练习
AC代码：

#include<stdio.h>
#include<string.h>
#define INF 0x11111111
int map[1010][1010];
int way[1010],flag[1010];
int main()
{
    int i,j,n,m,x,y,z,v,s,t;
    while(scanf("%d %d",&n,&m),n!=0&&m!=0)
    {
       memset(map,INF,sizeof(map));//数组初始化为最大值 
       for(i=0;i<m;i++)
       {
          scanf("%d %d %d",&x,&y,&z);
          map[x][y]=z;//储存正反向的路径长度和花费 
          map[y][x]=z;
       }      
       
       memset(way,INF,sizeof(way));//此数组储存从s到i的长度 
       
       memset(flag,0,sizeof(flag));//标记路径点是否被加入最短路径中 
       
       flag[1]=1;//起点已经被标记为加入最短路径
       
       for(i=1;i<=n;i++)//开始赋值 
       {
          way[i]=map[1][i];
       } 
       
       for(i=1;i<n;i++)
       {
          int min=INF;
          int k=0;
          for(j=1;j<=n;j++)//找出一个距离起点最近的路径
          {
             if(flag[j]==0&&way[j]<min) 
             {
                min=way[j];
                k=j;
             }
          } 
          
          flag[k]=1;
          for(j=1;j<=n;j++)//找出距离刚刚选出来的点最近的距离组成新的路径 
          {
             if(flag[j]==0&&way[k]+map[k][j]<way[j]) 
             {
                way[j]=way[k]+map[k][j];
             }
          }
       }
       
       printf("%d\n",way[n]);
    }
    return 0;
}

佛洛伊德算法（以前写的）：
AC代码：

#include<stdio.h>
#include<string.h>
#define MAX 105  //节点最多到100
#define INF 0x11111111 //定义一个初始地址
int i,j,n,m,x,y,z;//全局变量方便操作
typedef int num[MAX][MAX];//二维数组用来存路径
typedef int per[MAX][MAX];//用来对路径进行操作
num a;//num类型的二维数组a
per b;//per类型的二维数组b
void Shortway(num &a,per &b,int n)//最短路径函数
{
 int v,w,u;  
    for (v=0; v<n; ++v)        // 各对结点之间初始已知路径及距离   
    {  
        for (w=0; w<n; ++w) {  
            b[v][w] = a[v][w];  
        }  
        b[v][v] = 0;    // BUG 修正
    }  
    for (u=0; u<n; ++u)  
        for (v=0; v<n; ++v)  
            for (w=0; w<n; ++w)  
                if (b[v][u]+b[u][w] < b[v][w]) {  // 从v经u到w的一条路径更短   
                    b[v][w] = b[v][u]+b[u][w];  
                }  

}
int main()
{
 while(scanf("%d%d",&n,&m),n!=0&&m!=0)
 {
         memset(a,INF,sizeof(a));//二维数组初始化,给他们一个初始地址  
                memset(b,INF,sizeof(b)); 
  for(i=0;i<m;i++)
  {
   scanf("%d%d%d",&x,&y,&z);
          x--;y--;
   a[x][y]=z;//将正反路径带权都储存
   a[y][x]=z;
  }
  Shortway(a,b,n);
  printf("%d\n",b[0][n-1]);//输出0到n-1的最短路径
    }
 return 0;
}