#include <iostream>
#include <queue>
#define int long long
using namespace std;
const int N=2e5+5,M=2e5+5,inf=0x7fffffffffffffff;
struct edge{
int to,nxt,val;
}e[M];
int n,m,s,u,v,w;
int head[N],top;
int dist[N],vis[N];
priority_queue<pair<int,int>> q;
inline int read(){
int X=0; bool flag=1; char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
while(ch>='0' && ch<='9') X=(X<<1)+(X<<3)+ch-'0',ch=getchar();
if(flag) return X;
return ~(X-1);
}
inline void write(int X){
if(X<0) putchar('-'),X=~(X-1);
int s[20],top=0;
while(X) s[++top]=X%10,X/=10;
if(!top) s[++top]=0;
while(top) putchar(s[top--]+'0');
putchar(' ');
}
void add(int u,int v,int w){
top++;
e[top].to=v;
e[top].val=w;
e[top].nxt=head[u];
head[u]=top;
}
void dijkstra(){
for(int i=1; i<=n; i++){
dist[i]=inf;
}
dist[s]=0;
q.push(make_pair(0,s));
while(!q.empty()){
u=q.top().second;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u]; i; i=e[i].nxt){
v=e[i].to;
if(dist[v]>dist[u]+e[i].val){
dist[v]=dist[u]+e[i].val;
q.push(make_pair(-dist[v],v));
}
}
}
}
signed main(){
n=read(),m=read(),s=1;
while(m--){
u=read(),v=read(),w=read();
add(u,v,w);
}
dijkstra();
for(int i=1; i<=n; i++){
write(dist[i]==inf ? -1 : dist[i]);
}
return 0;
}
应该不用注释了吧…
rt,紫紫黑黑,不知道哪错了,求大佬帮查一下QwQ,这题就是板子题(我蒻