Floyd-Warshall算法使用DP方法来求解任意两点间的最短路问题。
i到j的最短路分正好经过顶点k一次和完全不经过顶点k两种情况来讨论。不断的进行d[i][j] = min(d[i][j], d[i][k] + d[k][j])的更新来实现，复杂度是O(n ^ 3)。
此算法可以处理负权边，也可以判断图中是否有负圈，只需检查是否存在d[i][i]是负数的顶点i就可以了。

//Floyd-Warshall
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int
MAXV = 105, MAXE = 10005, INF = 0x3f3f3f3f;

int v, e;
int d[MAXV][MAXV];

bool Floyd_Warshall() {
    for(int k = 1; k <= v; ++k) {
        for(int i = 1; i <=v; ++i) {
            for(int j = 1; j<= v; ++j) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    for(int i = 1; i <= v; ++i) 
        if(d[i][i] < 0)
            return false;
    return true; 
}
int main() {
    while(scanf("%d%d", &v, &e) != EOF && v && e) {
        for(int i = 1; i <= v; ++i) {
            for(int j = 1; j <= v; ++j) {
                d[i][j] = d[j][i] = (i == j ? 0 : INF);
            }
        }
        for(int i = 1; i <= e; ++i) {
            int f, t, c;
            scanf("%d%d%d",&f, &t, &c);
            d[f][t] = d[t][f] = c;
        }
        if(Floyd_Warshall())
            printf("%d\n", d[1][v]);
        else
            printf("有负圈\n");
    }
    return 0;
}