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.--