最短路 - dijkstra

const int inf = 1e5+5;  // 这个值要注意，避免越届
int edge[1005][1005];
int t, n, ans;
int d[1005];
bool used[1005];

void dij(){
    for(int i = 1; i <= n; i++){
        d[i] = inf;
    }    
    memset(used, false, sizeof(used));
    d[1] = 0;
    while(1){
        int v = -1;
        for(int i = 1; i <= n; i++){
            if (!used[i] && (v == -1 || d[i] < d[v])) v = i;
        }
        if (v == -1) break;
        used[v] = true;
        for(int i = 1; i <= n; i++){
            d[i] = min(d[i], d[v]+edge[v][i]);
        }
    }    
}

int main() {
    int a, b, c;
    
    while(~scanf("%d%d", &t, &n)){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if (i == j) edge[i][j] = 0;
                else edge[i][j] = inf;
            }
        }
        for(int i = 1; i <= t; i++){
            scanf("%d%d%d", &a, &b, &c);
            if (edge[a][b] > c)  // 寻求最短的边保存起来
                edge[a][b] = edge[b][a] = c;
        }
        dij();
        printf("%d\n", d[n]);
    }

    return 0;
}