洛谷 P3371 【模板】单源最短路径（弱化版） && dijkstra模板

嗯...

 

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

 

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

注意：

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

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

AC代码：

#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;
const int maxn = 500005;
int n, m, tot, s;
long long inf = 0x3f3f;
int vis[maxn], dis[maxn], e[maxn];
// vis -> 是否被访问过  dis -> 最短路  e -> 边的编号 
struct node{
    int next, to, from, val;
} g[maxn];

inline void add(int u, int v, int w){
    g[++tot].from = u;
    g[tot].next = e[u];
    e[u] = tot;
    g[tot].to = v;
    g[tot].val = w;
}//邻接表 

inline void dijkstra(int x){
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= n; i++) dis[i] = (i == x ? 0 : inf);//初始化 
    for(int i = 1; i <= n; i++){
        int t = 0, y = inf;
        for(int j = 1; j <= n; j++) if(!vis[j] && dis[j] <= y) y = dis[t = j];
        vis[t] = 1;
        for(int j = e[t]; j; j = g[j].next) dis[g[j].to] = min(dis[g[j].to], dis[t] + g[j].val);
    }//松弛操作 
    for(int i = 1; i <= n; i++) {if(dis[i] == 0x3f3f) printf("2147483647 "); else printf("%d ", dis[i]);}
}

int main(){
    memset(dis, 0x3f3f, sizeof(dis));
    scanf("%d%d%d", &n, &m, &s);
    for(int i = 1; i <= m; i++){
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);//单向图 
    }
    dijkstra(s);
    return 0;
}