社区讨论
求助!!!不知道错那。谢谢大佬
P4779【模板】单源最短路径(标准版)参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mi85yg4i
- 此快照首次捕获于
- 2025/11/21 09:10 4 个月前
- 此快照最后确认于
- 2025/11/21 09:10 4 个月前
CPP
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define MA 100005
#define Ma 500005
#define inf 0x7fffffff
using namespace std;
int n,m,s;
int fis[MA];
struct node{
int nex,go,dis;
}e[Ma];
bool vst[MA];
int d[MA];
int cnt;
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 x,int y,int w){
e[++cnt].nex=fis[x];
fis[x]=cnt;
e[cnt].go=y;
e[cnt].dis=w;
return ;
}
struct kkk{
int dis;
int pos;
bool operator <( const kkk &x )const
{
return x.dis<dis;
}
};
std::priority_queue<kkk>q;
inline void dijkstra(){
//memset(vst,false,sizeof(vst));
//memset(d,0x3f,sizeof(d));
d[s]=0;
q.push( (kkk){0,s} );
while(!q.empty()){
kkk eg=q.top();
q.pop();
int x=eg.pos,ds=eg.dis;
if(vst[x]){
continue;
}
vst[x]=true;
for(int i=fis[x];i;i=e[i].nex){
int y=e[i].go;
//int z=e[i].dis;
if(d[y]>d[x]+e[i].dis){
d[y]=d[x]+e[i].dis;
if(!vst[y]){
q.push( (kkk){d[y],y} );
}
}
}
}
return ;
}
int main(){
int i;
int x,y,w;
n=read();m=read();s=read();
for(i=1;i<=m;i++){
x=read();y=read();w=read();
add(x,y,w);
add(y,x,w);
}
for(i=1;i<=n;i++){
d[i]=inf;
}
dijkstra();
for(i=1;i<=n;i++){
printf("%d ",d[i]);
}
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...