学步园

flody
for(k=0; k<n; k++)  //中间节点
 for(i=0; i<n; i++) //起点
  for(j=0; j<n; j++) //重点

   map[i][j]=min(map[i][j], map[i][k]+map[k][j]);

例如HDU2544

# include<stdio.h>
# include<string.h>
# include<algorithm>

using namespace std;
const int INF = 99999;
const int maxn = 105;
int N, M;
int d[maxn];
int map[maxn][maxn];


int main(void)
{
    int i, j, k, A , B, C;
    while(scanf("%d%d", &N, &M)==2)
    {

        if(N==0 && M==0)
        break;
        for(i=1; i<=N; i++)
        for(j=1; j<=N; j++)
        map[i][j]=INF;
        for(i=1; i<=M; i++)
        {
            scanf("%d%d%d", &A, &B, &C);
            if(map[A][B]>C)
            map[A][B]=map[B][A]=C;
        }
        for(k=1; k<=N; k++)  //中间节点
          for(i=1; i<=N; i++) //起点
            for(j=1; j<=N; j++) //重点
              map[i][j]=min(map[i][j], map[i][k]+map[k][j]);
        printf("%d\n", map[1][N]);
    }


    return 0;
}