学步园

#include<stdio.h>
#include<string.h>
//#define inf 0x3fffffff//这个就wrong了
#define inf 99999999
int map[110][110],dis[110][110];
int main()
{
    int n,m,i,j,w,x,y,min,k;
    while(scanf("%d%d",&n,&m)!=-1)
    {
        for(i=1;i<=n;i++)
        {
            for(j=i+1;j<=n;j++)
            {
                map[i][j]=map[j][i]=inf;
                dis[i][j]=dis[j][i]=inf;
            }
            map[i][i]=0;
            dis[i][i]=0;
        }
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&x,&y,&w);
            if(map[x][y]>w)
            {
                map[x][y]=map[y][x]=w;
                dis[x][y]=dis[y][x]=w;
            }
        }
        min=inf;
        for(k=1;k<=n;k++)
        {
            for(i=1;i<k;i++)
                for(j=i+1;j<k;j++)
                {
                    if(min>dis[i][j]+map[i][k]+map[k][j])
                        min=dis[i][j]+map[i][k]+map[k][j];
                }
                for(i=1;i<=n;i++)
                    for(j=1;j<=n;j++)
                        if(dis[i][j]>dis[i][k]+dis[k][j])
                            dis[i][j]=dis[i][k]+dis[k][j];
        }
        if(min<inf)printf("%d\n",min);
        else printf("It's impossible.\n");
    }
    return 0;
}