社区讨论
蒟蒻求错
P4779【模板】单源最短路径(标准版)参与者 3已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @mi8616fa
- 此快照首次捕获于
- 2025/11/21 09:12 4 个月前
- 此快照最后确认于
- 2025/11/21 09:12 4 个月前
CPP
#include<iostream>
#include<cstdio>
#include<queue>
#define inf 0x7fffffff
#define MA 200005
using namespace std;
typedef pair<int,int>pi;
int n,m,s;
int fis[MA*2],nex[MA*2],go[MA*2],d[MA*2],tot;
int dis[MA>>1],vst[MA>>1],top;
pi h[MA*2];
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();};
while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();};
return x*f;
}
inline void add(int u,int v,int w){
nex[++tot]=fis[u];
fis[u]=tot;
go[tot]=v;
d[tot]=w;
return ;
}
inline void dijkstra(int x){
int i;
for(i=1;i<=n;i++){
dis[i]=inf;
vst[i]=0;
}
dis[x]=0;
vst[x]=1;
top=0;
for(i=1;i<=n;i++){
for(int e=fis[x];e;e=nex[e]){
int v=go[e];
if(dis[v]>dis[x]+d[e]){
dis[v]=dis[x]+d[e];
h[top++]=pi(-dis[v],v);
push_heap(h,h+top);
}
}
while(top){
pi cur=h[0];
pop_heap(h,h+top);
--top;
x=cur.second;
if(!vst[x]){
break;
}
if(!top){
return ;
}
}
vst[x]=1;
}
return ;
}
int main(){
int i;
int x,y,z;
n=read();m=read();s=read();
for(i=1;i<=m;i++){
x=read();y=read();z=read();
add(x,y,z);
add(y,x,z);
}
dijkstra(s);
for(i=1;i<=n;i++){
printf("%d ",dis[i]);
}
cout<<inf;
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...