擦,没有判重边wa了两发。。
#include <iostream> #include <stdlib.h> #include <stdio.h> #include <string.h> #include <math.h> #include <queue> #include <algorithm> using namespace std; const int maxn = 1010; const int inf = 0x3f3f3f3f; bool vis[maxn]; int map[maxn][maxn]; int dis[maxn]; int n, m; void dijkstra(int start) { dis[start] = 0; int now, mindis; for(int i = 0; i < n; i++) { mindis = inf; for(int j = 0; j < n; j++) { if(!vis[j] && mindis > dis[j]) { mindis = dis[j]; now = j; } } if(mindis >= inf) break; vis[now] = true; for(int j = 0; j < n; j++) { if(!vis[j] && dis[now] + map[now][j] < dis[j]) dis[j] = dis[now] + map[now][j]; } } } int main() { #ifdef BellWind freopen("1874.in", "r", stdin); #endif // BellWind while(~scanf("%d%d", &n, &m)) { int a, b, cost; int s, e; memset(vis, false, sizeof(vis)); memset(map, 0x3f, sizeof(map)); memset(dis, 0x3f, sizeof(dis)); for(int i = 0; i < m; i++) { scanf("%d%d%d", &a, &b, &cost); if(cost < map[a][b]) { map[a][b] = cost; map[b][a] = cost; } } scanf("%d%d", &s, &e); dijkstra(s); if(dis[e] >= inf) printf("-1\n"); else printf("%d\n", dis[e]); } return 0; }