2018年4月月赛 Day2 Violet 题解

2018年4月月赛 Day2 Violet 题解

题目背景

少佐在哪!!别拦着我!!我要去找少佐!! 自从那天的别离之后,Violet和少佐已经分别许久。就在Violet从昏迷中恢复意识的那一刻起,Violet一直在计划着去寻找少佐。

现在,时机成熟了。

题目描述

Violet只能确定少佐在n个城市中的某一个,却不知道具体在哪一个,而从疗养院所在地s去到任意一个城市,都需要经过若干城市之间的若干有向道路。这些道路错综复杂,Violet想尽快赶到。

请你帮她算算到各个城市的最短时间吧。

输入输出格式

输入格式

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

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

输出格式

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

输入输出样例

输入样例#1:

1
2
3
4
5
6
7
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

输出样例#1:

1
0 2 4 3

说明

1<=N<=10000,1<=M<=500000

邻接表板子题……

可类比Luogu P3371

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
struct edge{int next,dis;};
vector<edge> e[10010];
int ans[10010];
bool v[10010]={false};
queue<int>q;
inline void addedge(int f,int g,int w)
{
edge x;
x.next=g;
x.dis=w;
e[f].push_back(x);
}
void spfa()
{
while(!q.empty())
{
int t=q.front();
q.pop();
v[t]=false;
for(vector<edge>::iterator i=e[t].begin();i!=e[t].end();i++)
{
int tmp=ans[t]+i->dis,ttt=i->next;
if(tmp<ans[ttt])
{
ans[ttt]=tmp;
if(!v[ttt])
{
q.push(ttt);
v[ttt]=true;
}
}
}
}
}
int main()
{
int n,m,s;
cin>>n>>m>>s;
for(int i=1;i<=n;i++) ans[i]=2147483647;
ans[s]=0;
for(int i=0;i<m;i++)
{
int f,g,w;
scanf("%d %d %d",&f,&g,&w);
addedge(f,g,w);
}
q.push(s);
v[s]=true;
spfa();
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
return 0;
}
--It's the end.Thanks for your read.--