裸的最短路 dijkstra
#include#include #include #include using namespace std;const int MAXN = 101;const int INF = 0x3f3f3f3f;int dist[MAXN], vis[MAXN], mat[MAXN][MAXN];int main(){ int t, u, v, w, n, m, CASE(0); scanf("%d", &t); while(t--){ scanf("%d%d", &n, &m); memset(mat, 0x3f, sizeof mat); memset(dist, 0x3f, sizeof dist); for(int i = 0;i < m;i ++){ scanf("%d%d%d", &u, &v, &w); mat[u][v] = mat[v][u] = min(mat[u][v], w); } dist[1] = 0; memset(vis, 0, sizeof vis); vis[1] = 1; for(int i = 1;i <= n;i ++) if(mat[1][i] != INF) dist[i] = mat[1][i]; for(int i = 0;i < n;i ++){ int minn(INF), k(-1); for(int j = 1;j <= n;j ++){ if(!vis[j] && minn > dist[j]){ minn = dist[j]; k = j; } } if(k == -1) break; vis[k] = 1; for(int j = 1;j <= n;j ++){ if(!vis[j] && mat[k][j] + dist[k] < dist[j]) dist[j] = mat[k][j] + dist[k]; } } printf("Case %d: ", ++CASE); if(dist[n] == INF) printf("Impossible\n"); else printf("%d\n", dist[n]); } return 0;}