最短路算法（Floyd）

HDU 2544 用作測試模闆是否正确

#include<cstdio>

const int inf = 0xfffff; 
const int N = 510;
int dis[N][N];

void initi(int n){
	int i, j;
	for(i = 0;i < n;i++)  
 		for(j = 0;j < n;j++)  
   			dis[i][j] = inf;  
}

int floyd(int n){
	int i, j, k;
	for (k = 0;k < n;k++)  
 		for (i = 0;i < n;i++)  
			for (j = 0;j < n;j++)  
   				if (dis[i][j] > dis[i][k] + dis[k][j])  
  					dis[i][j] = dis[i][k] + dis[k][j]; 
	return dis[0][n - 1]; 
}

int main(){  
    int n, m;  
    while(scanf("%d%d", &n, &m)){  
        int j, temp, A, B, C; 
		if(n == 0&&m == 0)
			break; 
        initi(n);
        for(j = 0;j < m;j++){  
            scanf("%d%d%d", &A, &B, &C);  
            dis[A - 1][B - 1] = C;  
            dis[B - 1][A - 1] = C;  
        }  
        printf("%d\n", floyd(n));  
    }     
    return 0;  
}