P3371 【模板】单源最短路径

题目描述

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

输入输出格式

输入格式:

第一行包含三个整数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

样例说明:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 using namespace std;
 7 const int MAXN=500001;
 8 struct node
 9 {
10     int u;
11     int v;
12     int w;
13     int next;
14 }edge[MAXN];
15 int num=1;
16 int head[MAXN];
17 void add(int x,int y,int z)
18 {
19     edge[num].u=x;
20     edge[num].v=y;
21     edge[num].w=z;
22     edge[num].next=head[x];
23     head[x]=num++;
24 }
25 int dis[MAXN];
26 int vis[MAXN];
27 int n,m,s;
28 void SPFA(int s)
29 {
30     dis[s]=0;
31     vis[s]=1;
32     queue<int>q;
33     q.push(s);
34     while(q.size()!=0)
35     {
36         int p=q.front();
37         q.pop();
38         vis[p]=0;
39         for(int i=head[p];i!=-1;i=edge[i].next)
40         {
41             int to=edge[i].v;
42             if(dis[to]>dis[p]+edge[i].w)
43             {
44                 dis[to]=dis[p]+edge[i].w;
45                 if(vis[to]==0)
46                 {
47                     q.push(to);
48                     vis[to]=1;
49                 }
50             }
51         }
52     }
53     for(int i=1;i<=n;i++)
54     {
55         printf("%d ",dis[i]); 
56     }
57 }
58 int main()
59 {
60     
61     scanf("%d%d%d",&n,&m,&s);
62     for(int i=1;i<=n;i++)head[i]=-1,dis[i]=2147483647;
63     for(int i=1;i<=m;i++)
64     {
65         int x,y,z;
66         scanf("%d%d%d",&x,&y,&z);
67         add(x,y,z);
68     }
69     SPFA(s);
70     return 0;
71 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏DannyHoo的专栏

OC中内存管理的一些问题

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u010105969/article/details/...

1433
来自专栏前端儿

表达式求值

ACM队的mdd想做一个计算器,但是,他要做的不仅仅是一计算一个A+B的计算器,他想实现随便输入一个表达式都能求出它的值的计算器,现在请你帮助他来实现这个计算器...

1282
来自专栏闵开慧

java概念1

public static void main(String[] args) {//其中[]也可以写在args后面,args也可以随便写成其他字母,例如asd...

36111
来自专栏Python绿色通道

Python入门三部曲(二)

如果不确定使用del语句还是pop()方法,有一个简单的标准:如果你要从列表中删除的一个元素,且不再以任何方式使用它,就使用del语句;如果你要在删除元素后还能...

1173
来自专栏绿巨人专栏

[Java] 设计模式: Code Shape - 管理你的代码结构

4456
来自专栏Java开发者杂谈

java如何获取一个对象的大小

When---什么时候需要知道对象的内存大小 在内存足够用的情况下我们是不需要考虑java中一个对象所占内存大小的。但当一个系统的内存有限,或者某块程序代码允许...

1.4K7
来自专栏数据结构与算法

病毒

【问题描述】   有一天,小y突然发现自己的计算机感染了一种病毒!还好,小y发现这种病毒很弱,只是会把文档中的所有字母替换成其它字母,但并不改变顺序,也不会增加...

5557
来自专栏xx_Cc的学习总结专栏

iOS底层原理总结 - 探寻block的本质(二)

3024
来自专栏数据结构与算法

BZOJ1901: Zju2112 Dynamic Rankings(整体二分 树状数组)

给定一个含有n个数的序列a[1],a[2],a[3]……a[n],程序必须回答这样的询问:对于给定的i,j,k,在a[i],a[i+1

872
来自专栏小灰灰

JDK容器学习之Queue: ArrayDeque

数组双端队列 ArrayDeque 双端队列,表示可以添加元素到(或删除,获取)队列头也可以添加元素到(或删除,获取)队列尾 ? 1. 底层数据结构 类中定义成...

2166

扫码关注云+社区

领取腾讯云代金券