ForMyDream @ 2022-07-01 09:35:00
#include<bits/stdc++.h>
#define maxn 500005
using namespace std;
struct Edge{
int u,v,w,next;
}edge[maxn*2];
int n,m,cnt,head[maxn*2];//cnt:表示有多少条边
void add(int u,int v,int w){
cnt++;
edge[cnt].u=u;
edge[cnt].v=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt;
}
int dis[maxn],vis[maxn],s=1; //vis[s]=1,表示s是黄点
struct qnode{
int v,length;//s---v的长度
bool operator <(const qnode &r) const{
return r.length<length;
}
};
void dijkstra(){//m*logn
// memset(dis,0x7fffffff,sizeof(dis));
dis[s]=0;
priority_queue<qnode> que;//元素:点的编号,和到s的值
que.push((qnode){s,0});
//找到入伙的点,用改点去更新其他的dis值
while(!que.empty()){
qnode temp=que.top();//就是距离最短的值 logn
que.pop();
int u=temp.v;
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];i;i=edge[i].next){
//更新相应的s到其他点的最小值
int v=edge[i].v;//v==3
if(vis[v]==0&&dis[v]>dis[u]+edge[i].w){
dis[v]=dis[u]+edge[i].w;
que.push( (qnode){v,dis[v]} );
}
}
}
}
int main(){
cin>>n>>m>>s;
for(int i = 1; i <= n; ++i)dis[i] = 0x3f3f3f3f;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);
add(v,u,w);
}
dijkstra();
for(int i=1;i<=n;i++){
if(dis[i]==0x3f3f3f3f)
cout<<-1<<' ';
else
cout<<dis[i]<<' ';
}
return 0;
}
by DrBit @ 2022-07-01 09:51:25
(这题不是单向边吗
by ForMyDream @ 2022-07-01 10:05:06
@DrBit 我太粗心了,已经AC,谢谢大佬