当前位置: 代码迷 >> 综合 >> 洛谷 P3371 [模版] 单源最短路径
  详细解决方案

洛谷 P3371 [模版] 单源最短路径

热度:93   发布时间:2024-01-19 02:53:19.0

题目描述

如题,给出一个有向图,请输出从某一点出发到所有点的最短路径长度。

输入输出格式

输入格式:

第一行包含三个整数N、M、S,分别表示点的个数、有向边的个数、出发点的编号。

接下来M行每行包含三个整数Fi、Gi、Wi,分别表示第i条有向边的出发点、目标点和长度。

输出格式:

一行,包含N个用空格分隔的整数,其中第i个整数表示从点S出发到点i的最短路径长度(若S=i则最短路径长度为0,若从点S无法到达点i,则最短路径长度为2147483647)

输入输出样例

输入样例#1:
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 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

样例说明:


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

裸的SPFA~

看到了这么一道水题,赶紧写了一下,……华丽丽地T了……

把vector改成数组模拟的,还是T……

然后数组改成结构体,还是T……

最后发现是嵌套的if写成并列的了……

所以我真的没有在水博……

就这道SPFA,我T了一个小时……

(感觉我该复习模板了……[泪])

(另外,memset(f,127,sizeof(f)) 一下,出来的f的值是maxint=2139062143,好神奇啊~)


#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;int n,m,s,x,y,vv,fir[500001],ne[500001],w[500001],v[500001],cnt,f[10001];
bool b[500001];
queue<int> q;int main()
{scanf("%d%d%d",&n,&m,&s);memset(f,127,sizeof(f));for(int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&vv);v[++cnt]=vv;w[cnt]=y;ne[cnt]=fir[x];fir[x]=cnt;}q.push(s);b[s]=1;f[s]=0;while(!q.empty()){int kkz=q.front();q.pop();b[kkz]=0;for(int i=fir[kkz];i;i=ne[i]){int z=w[i];if(f[z]>f[kkz]+v[i]){f[z]=f[kkz]+v[i];if(!b[z]) b[z]=1,q.push(z);}}}for(int i=1;i<=n;i++)if(f[i]==2139062143) printf("2147483647 ");else printf("%d ",f[i]);return 0;
}