首页 > 代码库 > Luogu P3371 【模板】单源最短路径
Luogu P3371 【模板】单源最短路径
题目描述
如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。
输入输出格式
输入格式：
第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。
接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度。
输出格式：
一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的最短路径长度（若S=i则最短路径长度为0，若从点S无法到达点i，则最短路径长度为2147483647）
输入输出样例
输入样例#1：
4 6 11 2 22 3 22 4 11 3 53 4 31 4 4
输出样例#1：
0 2 4 3
说明
时空限制：1000ms,128M
数据规模：
对于20%的数据：N<=5，M<=15
对于40%的数据：N<=100，M<=10000
对于70%的数据：N<=1000，M<=100000
对于100%的数据：N<=10000，M<=500000
样例说明：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 ll read() 5 { 6 ll ret=0,ok=1; 7 char ch=getchar(); 8 while(ch<‘0‘||ch>‘9‘) 9 {10 if(ch==‘-‘)ok=-1;11 ch=getchar();12 }13 for(;ch>=‘0‘&&ch<=‘9‘;ch=getchar())14 ret=ret*10+ch-‘0‘;15 return ret*ok;16 }17 const ll maxn=500000+10;18 const ll INF=~0u>>1;19 ll head[maxn],to[maxn],v[maxn],w[maxn],num,dis[maxn],vis[maxn],n,m,s,ans;20 struct node{21 ll d,pos;22 bool operator < (const node&pd) const {23 return d>pd.d;24 }25 }tmp;26 inline void get_node()27 {28 ll U,V,W;29 U=read(),V=read(),W=read();30 to[++num]=head[U],head[U]=num,v[num]=V,w[num]=W;31 }32 priority_queue <node> q;33 int main()34 {35 n=read(),m=read(),s=read();36 for(ll i=0;i<m;i++)37 dis[i]=INF;38 for(int i=1;i<=m;i++)39 get_node();40 dis[s]=0;41 q.push((node){0,s});42 while(!q.empty()){43 tmp=q.top();44 q.pop();45 ll uu=tmp.pos;46 if(vis[uu])47 continue;48 for(int h=head[tmp.pos],o=v[h];h;o=v[h=to[h]])49 {50 if(dis[o]>dis[uu]+w[h]){51 dis[o]=dis[uu]+w[h];52 q.push((node){dis[o],o});53 } 54 }55 vis[uu]=1; 56 }57 for(int i=1;i<=n;i++)58 cout<<dis[i]<<" ";59 return 0;60 }
Luogu P3371 【模板】单源最短路径
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。