嗯...

 

题目链接：https://www.luogu.org/problem/P1339

 

这道题是水的不能在水的裸最短路问题...这里用的dijkstra

 

但是自己进了一个坑——

　　因为有些城市之间可能还没有道路，自己只是将其初始化为0，而应该初始化为0x3f3f，从而表示两个城市之间没有道路...

 

AC代码：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5  6 using namespace std; 7 const int inf = 0x3f3f; 8 int n, c, ts, te, dis[2505], vis[2505], g[5005][5005]; 9 10 inline void dijkstra(int x){11     for(int i = 1; i <= n; i++) dis[i] = (i == x ? 0 : inf);12     for(int i = 1; i <= n; i++){13         int t = 0, y = inf;14         for(int j = 1; j <= n; j++) if(!vis[j] && dis[j] <= y) y = dis[t = j]; 15         vis[t] = 1;16         for(int j = 1; j <= n; j++) dis[j] = min(dis[j], dis[t] + g[t][j]);17     }18 }19     20 21 int main(){22     memset(g, 0x3f3f, sizeof(g));//初始化！！23     scanf("%d%d%d%d", &n, &c, &ts, &te);24     for(int i = 1; i <= c; i++){25         int u, v, w;26         scanf("%d%d%d", &u, &v, &w);27         g[u][v] = g[v][u] = w;28     }29     dijkstra(ts);30     printf("%d", dis[te]);31     return 0;32 }