Chen20090918 @ 2024-02-01 15:35:21
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define N 20001
struct nn{
int next,w,v;
}e[N];
int n,m,k=1,head[N],dis[N];
bool vis[N];
void add(int u,int v,int w){
e[k].v=v;
e[k].w=w;
e[k].next=head[u];
head[u]=k++;
}
void dij(){
typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii> >q;
dis[1]=0;
q.push(make_pair(dis[1],1));
while(!q.empty()){
int f=q.top().second;
q.pop();
if(vis[f])continue;
vis[f]=true;
for(int i=head[f];i!=-1;i=e[i].next){
int v=e[i].v;
if(dis[v]>dis[f]+e[i].w){
dis[v]=dis[f]+e[i].w;
}
q.push(make_pair(dis[v],v));
}
}
}
signed main(){
memset(vis,false,sizeof(vis));
memset(dis,1000000000,sizeof(dis));
memset(head,-1,sizeof(head));
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);
}
dij();
for(int i=1;i<=n;i++){
cout<<dis[i]<<' ';
}
return 0;
}
by kjhhjki @ 2024-02-01 15:45:03
by Chen20090918 @ 2024-02-01 16:55:58
@kjhhjki 感谢,已AC