求助堆优Dijkstra模版
  • 板块学术版
  • 楼主liuzimingc
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/4/9 19:24
  • 上次更新2023/11/5 00:49:19
查看原帖
求助堆优Dijkstra模版
421781
liuzimingc楼主2021/4/9 19:24

rt,为什么输出0 inf inf inf啊!

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define re register
#define endl '\n'
#define inf 2147483647
#define MAXN 100005
#define MAXM 200005

int n,m,s,x,y,z,tot;
struct edge {int v,w,nex;};
edge e[MAXM];
int head[MAXN],dis[MAXN];

inline void add(int u,int v,int w) {e[++tot]=(edge){v,w,head[u]};head[u]=tot;}

struct node {
    int u,d;
    bool operator <(const node& as)const {return d>as.d;}
};

inline void dijkstra() {
    for (re int i=1;i<=n;i++) dis[i]=inf;dis[s]=0;
    priority_queue<node>q;
    while (!q.empty()) {
        int u=q.top().u,d=q.top().d;q.pop();
        if (d!=dis[u]) continue;
        for (re int i=head[u];i;i=e[i].nex) {
            int v=e[i].v,w=e[i].w;
            if (dis[u]+w<dis[v]) {dis[v]=dis[u]+w;q.push((node){v,dis[v]});}
        }
    }
}
int main() {
    cin>>n>>m>>s;
    while (m--) {
        cin>>x>>y>>z;
        add(x,y,z);
    }
    dijkstra();
    for (re int i=1;i<=n;i++) cout<<dis[i]<<" ";
    return 0;
}
2021/4/9 19:24
加载中...