hdu-2544

版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/41092657

floyd

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<ctype.h>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include <string>
#include <sstream>
#include <time.h>

using namespace std;

int d[1010][1010];

int main ()    
{
    int n,m;
    while (scanf ("%d %d",&n,&m)!=EOF && n)
    {
        for (int i=0;i<=n;i++)
            for (int j=0;j<=n;j++)
            {
                d[i][j]=1000001;
            }

        int a,b,c;

        for (int i=0;i<m;i++)
        {
            scanf ("%d%d%d",&a,&b,&c);
            d[a][b]=d[b][a]=c;
        }

        for (int k=1;k<=n;k++)
            for (int i=1;i<=n;i++)
                for (int j=1;j<=n;j++)
                {
                    if (  d[i][j] > ( d[i][k]+d[k][j]) )
                        d[i][j] = ( d[i][k]+d[k][j] );
                }

        printf ("%d\n",d[1][n]);
    }
    return 0;
}