题目背景
本题测试数据为随机数据, 在考试中可能会出现构造数据让 SPFA 不通过, 如有需要请移步 https://www.luogu.org/problemnew/show/P4779 .
题目描述
如题, 给出一个有向图, 请输出从某一点出发到所有点的最短路径长度.
输入输出格式
输入格式:
第一行包含三个整数 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. 保证数据随机.
对于真正 100% 的数据, 请移步 https://www.luogu.org/problemnew/show/P4779 . 请注意, 该题与本题数据范围略有不同.
样例说明:
题解: 真. 模板题, 真的只是套模板啊啊啊! dijkstra 算法
- #include<cstdio>
- #include<iostream>
- #include<cmath>
- #include<cstdlib>
- #include<cstring>
- #include<algorithm>
- typedef long long ll;
- const int oo=2147483647;
- using namespace std;
- struct node{
- int z;
- int val;
- int nexty;
- }e[500005];
- int head[10004];
- int cnt=0;
- inline void add(int a,int b,int c){
- cnt++;
- e[cnt].z=b;
- e[cnt].val=c;
- e[cnt].nexty=head[a];
- head[a]=cnt;
- }
- bool v[10004];
- ll dis[20000];
- int n,m,s,a,b,c;
- int main(){
- freopen("3371.in","r",stdin);
- freopen("3371.out","w",stdout);
- scanf("%d %d %d",&n,&m,&s);
- for(int i=1;i<=n;i++)
- dis[i]=oo;
- for(int i=0;i<m;i++){
- scanf("%d %d %d",&a,&b,&c);
- add(a,b,c);
- }
- int curr=s;
- dis[s]=0;
- ll mn;
- while(!v[curr]){
- v[curr]=true;
- for(int i=head[curr];i!=0;i=e[i].nexty){
- if(!v[e[i].z]&&dis[e[i].z]>dis[curr]+e[i].val)
- dis[e[i].z]=dis[curr]+e[i].val;
- }
- mn=oo;
- for(int i=1;i<=n;i++){
- if(!v[i]&&mn>dis[i]){
- mn=dis[i];
- curr=i;
- }
- }
- }
- for(int i=1;i<=n;i++)
- printf("%lld",dis[i]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3111669.html