Forose @ 2023-12-24 10:56:38
#include<cstdio>
#include<queue>
using namespace std;
const int N=2e5+10;
int n,m,s;
long long ans[N];
int vis[N],head[N],cnt;
struct edge{
int to,next,dis;//to:儿子 next:兄弟 dis:权值
}kun[N];
struct node{
int ans,id;//ans值 点的编号
bool operator <(const node &x)const
{
return x.ans<ans;
}//要背 重载运算符
};
void add(int u,int v,int d){//起点 终点 权值
cnt++;
kun[cnt].next=head[u];//确定兄弟
kun[cnt].to=v;//终点
kun[cnt].dis=d; //权值
head[u]=cnt; //更新
} //存图
priority_queue<node> q; //堆
void Dijstra(){
ans[s]=0;
q.push( (node) {0,s});//node为强转
for(int i=0;i<N;i++) ans[i]=1e9;//初始化
while(!q.empty()){
node hp=q.top();
q.pop();
int idn=hp.id,ansn=hp.ans;
if(vis[idn]==0){//如果未访问过
vis[idn]=1;//标记
for(int i=head[idn];i!=0;i=kun[i].next){//枚举
int ypy=kun[i].to;
if(ans[idn]+kun[i].dis<ans[ypy]){//松弛操作
ans[ypy]=ans[idn]+kun[i].dis;
if(vis[ypy]==0){
q.push( (node){ans[ypy],ypy});
}
}
}
}
}
}
int main(){
scanf("%d %d %d",&n,&m,&s);
for(int i=1;i<=m;i++){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
add(a,b,c);
}
Dijstra();
for(int i=1;i<=n;i++){
printf("%d ",ans[i]);
}
return 0;
}
by __ZTY__ @ 2023-12-24 15:34:36
ans[s]=0;
q.push( (node) {0,s});//node为强转
for(int i=0;i<N;i++) ans[i]=1e9;//初始化
初始化把ans的值覆盖了