嗯...

 

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

 

没什么好说的，这是一个最短路的模板，这里用的dijkstra做的...

 

注意：

1.dijkstra和邻接表一块有点别扭，但还是可以遍历的...

2.dis数组不能初始化为2147483647，而要初始化0x3f3f，最后判一下还是不是0x3f3f即可

 

AC代码：

1 #include
      
        2 #include
       
         3 #include
        
          4  5 using namespace std; 6 const int maxn = 500005; 7 int n, m, tot, s; 8 long long inf = 0x3f3f; 9 int vis[maxn], dis[maxn], e[maxn];10 // vis -> 是否被访问过  dis -> 最短路  e -> 边的编号 11 struct node{12     int next, to, from, val;13 } g[maxn];14 15 inline void add(int u, int v, int w){16     g[++tot].from = u;17     g[tot].next = e[u];18     e[u] = tot;19     g[tot].to = v;20     g[tot].val = w;21 }//邻接表 22 23 inline void dijkstra(int x){24     memset(vis, 0, sizeof(vis));25     for(int i = 1; i <= n; i++) dis[i] = (i == x ? 0 : inf);//初始化 26     for(int i = 1; i <= n; i++){27         int t = 0, y = inf;28         for(int j = 1; j <= n; j++) if(!vis[j] && dis[j] <= y) y = dis[t = j];29         vis[t] = 1;30         for(int j = e[t]; j; j = g[j].next) dis[g[j].to] = min(dis[g[j].to], dis[t] + g[j].val);31     }//松弛操作 32     for(int i = 1; i <= n; i++) {
    if(dis[i] == 0x3f3f) printf("2147483647 "); else printf("%d ", dis[i]);}33 }34 35 int main(){36     memset(dis, 0x3f3f, sizeof(dis));37     scanf("%d%d%d", &n, &m, &s);38     for(int i = 1; i <= m; i++){39         int u, v, w;40         scanf("%d%d%d", &u, &v, &w);41         add(u, v, w);//单向图 42     }43     dijkstra(s);44     return 0;45 }