首页 > 代码库 > 洛谷 P 3371 单元最短路
洛谷 P 3371 单元最短路
题目描述
如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。
输入输出格式
输入格式：
第一行包含三个整数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
样例说明：
60分SPFA代码存档：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 #define MAXN 2147483647 6 #define N 10010 7 using namespace std; 8 struct node{ 9 int u,v,w;10 int next;11 }e[500010];12 int n,m,s,head[N],dis[N],ei;13 bool exist[N];14 void add(int u,int v,int w){15 e[++ei].u=u;e[ei].v=v;e[ei].w=w;16 e[ei].next=head[u];head[u]=ei;17 }18 queue<int> q;19 int main()20 {21 scanf("%d%d%d",&n,&m,&s);22 memset(dis,0x3f3f3f3f,sizeof(dis));23 memset(exist,false,sizeof(exist));24 for(int i=1,x,y,z;i<=m;i++){25 scanf("%d%d%d",&x,&y,&z);26 add(x,y,z);27 }28 exist[s]=true;dis[s]=0;q.push(s);29 while(!q.empty()){30 int p=q.front();q.pop();exist[p]=false;31 for(int i=head[p];i;i=e[i].next){32 int v=e[i].v;33 if(dis[v]>dis[p]+e[i].w){34 dis[v]=dis[p]+e[i].w;35 if(!exist[v]){36 q.push(v);37 exist[v]=true;38 }39 }40 }41 }42 for(int i=1;i<=n;i++){43 if(dis[i]==0x3f) printf("%d ",MAXN);44 else printf("%d ",dis[i]);45 }46 return 0;47 }
head数组开大一点，就成90了
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 #define MAXN 2147483647 6 #define N 10010 7 using namespace std; 8 struct node{ 9 int u,v,w;10 int next;11 }e[500010];12 int n,m,s,head[500010],ei;13 long long dis[N];14 bool exist[N];15 void add(int u,int v,int w){16 e[++ei].u=u;e[ei].v=v;e[ei].w=w;17 e[ei].next=head[u];head[u]=ei;18 }19 queue<int> q;20 int main()21 {22 scanf("%d%d%d",&n,&m,&s);23 memset(dis,0x3f3f3f3f,sizeof(dis));24 memset(exist,false,sizeof(exist));25 for(int i=1,x,y,z;i<=m;i++){26 scanf("%d%d%d",&x,&y,&z);27 add(x,y,z);28 }29 exist[s]=true;dis[s]=0;q.push(s);30 while(!q.empty()){31 int p=q.front();q.pop();exist[p]=false;32 for(int i=head[p];i;i=e[i].next){33 int v=e[i].v;34 if(dis[v]>dis[p]+e[i].w){35 dis[v]=dis[p]+e[i].w;36 if(!exist[v]){37 q.push(v);38 exist[v]=true;39 }40 }41 }42 }43 for(int i=1;i<=n;i++){44 if(dis[i]==0x3f3f3f3f) printf("%lld ",MAXN);45 else printf("%lld ",dis[i]);46 }47 return 0;48 }
洛谷 P 3371 单元最短路
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。