最短:Floydアルゴリズム

さいたんらく
Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 50349    Accepted Submission(s): 22136
Problem Description
毎年の学校試合では、決勝戦に進出したすべての学生がきれいなt-shirtを獲得します.しかし、私たちのスタッフが100枚以上の服を店から競技場に運ぶたびに、とても疲れました.だから今、彼らは店から競技場までの最短ルートを探しています.あなたは彼らを助けることができますか?
 
Input
入力には複数のデータが含まれます.各グループのデータの1行目は2つの整数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つの商店が競技場までのルートが存在する.
 
Output
各グループの入力に対して、1行出力し、従業員が店から競技場まで歩いた最短時間を示す.
 
Sample Input

   
   
   
   

    
    
    
    2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    3
2
   
   
   
   
   
   
   
   

    
    
    
        ,          .                   ,           .    floyd     .
   
   
   
   
   
   
   
   

    
    
    
             floyd   .       :                         ,                ,        .                ,        1  2       .....    1-n         ,            .         : i    j       k        .             .
    
    
    
    
#include <stdio.h>
#include <iostream>
using namespace std;
int a[102][102];
int main()
{
    int n,m,inf=999999;
    while(scanf("%d%d",&n,&m)&&n&&m)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(i==j)
                {
                    a[i][j]=0;
                }
                else
                {
                    a[i][j]=inf;
                }
            }
        }
        for(int i=1; i<=m; i++)
        {
            int k,l,c;
            cin>>k>>l>>c;
            a[k][l]=c;
            a[l][k]=c;
        }
        for(int k=1; k<=n; k++)
        {
            for(int i=1; i<=n; i++)
            {
                for(int 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[n][1]<<endl;


    }
    return 0;
}