Wei_scky @ 2024-09-18 14:38:21
rt
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int n,m,s;
int dis[N],to[N],w[N],nxt[N],head[N],k;
bool vis[N];
void add(int x,int y,int val) {
to[k]=y;
w[k]=val;
nxt[k]=head[x];
head[x]=k++;
}
void dijkstra() {
memset(dis,0x3f,sizeof dis);
// memset(vis,0,sizeof vis);
memset(head,-1,sizeof head);
dis[s]=0;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
q.push({0,s});
while(!q.empty()) {
pair<int,int> t=q.top();
q.pop();
int v=t.second,cnt=t.first;
if(vis[v]) continue;
vis[v]=true;
for(int i=head[v]; ~i; i=nxt[i]) {
if(dis[to[i]]>cnt+w[i]) {
dis[to[i]]=cnt+w[i];
q.push({dis[to[i]],to[i]});
}
}
}
}
signed main() {
scanf("%d%d%d",&n,&m,&s);
for(int i=1; i<=m; i++) {
int x,y,z;
cin>>x>>y>>z;
add(x,y,z);
}
dijkstra();
for(int i=1; i<=n; i++)
cout<<dis[i]<<" ";
return 0;
}
by Jarstick @ 2024-09-18 14:39:34
@Wei_scky 我太犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇! 你太蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻! 哈哈哈
by kinghku_dzk @ 2024-09-18 14:40:58
@Wei_scky 我太犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇! 你们太蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻! 哈哈哈
by Klayon @ 2024-09-18 14:43:03
@Wei_scky 我太犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇! 你太蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻! 哈哈哈
by RainBow_doge @ 2024-09-18 14:43:38
@Wei_scky 我太犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇! 你太蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻! 哈哈哈
by Wei_scky @ 2024-09-18 14:44:26
???
by 幻想繁星 @ 2024-09-18 14:45:01
@Wei_scky 你为什么要清空链式前向星
by Teamo_me @ 2024-09-18 14:45:16
@Wei_scky 我太犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇! 你太蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻! 哈哈哈
by Wei_scky @ 2024-09-18 14:47:36
@幻想繁星 谢谢,A了,已关
by Yaakov @ 2024-09-18 14:48:22
@Wei_scky 我太犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇! 你太蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻! 哈哈哈
by Jarstick @ 2024-09-18 14:48:54
@Wei_scky 当你背极地时阿拉斯加的单词正拂过费城 当你解水面时微分的海鸥正跃出方程 当你大洋彼岸时 晚自习五彩斑斓的夜空散满了鳕鱼