lwthree @ 2024-10-20 13:11:37
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 200005
int nxt[N],to[N],head[N],edge[N],cnt;
int dis[N],vis[N];
int n,m,s;
void add(int u,int v,int w){
nxt[++cnt]=head[u];
head[u]=cnt;
to[cnt]=v;
edge[cnt]=w;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>n>>m>>s;
int u,v,w;
cnt=0;
for (int i=1;i<=m;i++){
cin>>u>>v>>w;
add(u,v,w);
}
priority_queue<int> q;
memset(dis,0x3f,sizeof(dis));
dis[s]=0;
q.push(s);
while (!q.empty()){
int u=q.top();
q.pop();
if (vis[u]) continue;
vis[u]=1;
for (int i=head[u];i;i=nxt[i]){
int v=to[i],w=edge[i];
if (dis[v]>dis[u]+w) {
dis[v]=dis[u]+w;
if (!vis[v]) q.push(v);
}
}
}
for (int i=1;i<=n;i++){
cout<<dis[i]<<' ';
}
return 0;
}by Tiffake @ 2024-10-20 13:26:03
你为什么用这个优先队列存下标？
by masonxiong @ 2024-10-20 13:26:53
@lwthree
《优先队列存下标》
by Tiffake @ 2024-10-20 13:30:06
@lwthree 正确代码：
#define fst first
#define snd second
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
void dj(){
q.push({0,s});
while (!q.empty()){
pair<int,int> u=q.top();
q.pop();
if (vis[u.snd]) continue;
vis[u.snd]=1;
for (int i=head[u.snd];i;i=nxt[i]){
int v=to[i],w=edge[i];
if (dis[v]>dis[u.snd]+w) {
dis[v]=dis[u.snd]+w,q.push({dis[v],v});
}
}
}
}by lwthree @ 2024-10-20 13:40:06
哦哦哦哦哦哦哦
by Huangjh1 @ 2024-10-20 19:10:47
不能用优先队列存下标...