2020工大杯题解-E

发表于 更新于 分类于 本文字数： 1k 阅读时长 ≈ 4 分钟

**个人题解，和比赛官方无关，仅供参考

2020工大杯题解 - F - L 同学的程序课

题目描述

上完体育课之后，L同学接下来要上程序课。程序课自然离不开写代码，而写代码也离不开修BUG。虽然L同学十分优秀，但是也难逃与BUG斗争的命运。

所幸，L同学在与BUG的长时间较量中，积累了不少的经验。他发现他的程序可能出现的BUG共有N种。对于这些BUG，L同学掌握了K种方法，每种方法可以彻底修复一个$A_i$类BUG，这需要花费$T_{1i}$的时间。

但对于大部分BUG而言彻底修复是很困难的，在修复的过程中往往会产生一个新的BUG。对此，L同学还掌握了M种方法，每种方法可以修复一个$B_j$类BUG，但同时会产生一个$C_j$类BUG，这需要花费$T_{2j}$的时间。

现在，为了能尽快的完成程序课作业，L同学希望能够知道使用他目前所掌握的方法，彻底修复一个第x类BUG所需要的最短时间是多少。由于L同学学业繁忙，所以只能由你来帮助他了。

输入

第一行，三个整数N、K、M，分别代表一共有N种BUG（BUG的编号从1到N）、L同学掌握K种能够彻底修复一个BUG的方法，和M种在产生一个新BUG的情况下修复一个BUG的方法。

而后K行，每行两个整数$A_i$、$T_{1i}$，代表L同学掌握一种方法能够用$T_{1i}$的时间彻底修复一个$A_i$类BUG。

而后M行，每行三个整数$B_j$、$C_j$、$T_{2j}$，代表L同学掌握一种方法能够用$T_{2j}$的时间将一个$B_j$类BUG修复，但同时会产生一个$C_j$类BUG。

输出

共一行，用空格隔开的N个整数，第x个整数代表使用L同学使用掌握的方法彻底修复一个第x类BUG需要的最短时间。特别地，如果使用现有的方法无法彻底修复第x类的BUG，请在对应位置输出”INF”。

数据规模

对于100%的数据有：

$1 \leq N \leq 10^5$

$0 \leq K,M \leq 2*10^5$

$0 \leq K+M \leq 2*10^5$

$1 \leq A_i,B_j,C_j \leq N$

$1 \leq T_{1i},T_{2j} \leq 10^4$

$1 \leq \sum_{i=1}^{K}T_{1i}+\sum_{j=1}^{M}T_{2j} \leq 10^9$

输入输出样例

Input

1
2
3
4
5
6
7
8
5 3 4
1 3
2 9
5 1
1 3 4
4 2 5
1 2 2
2 5 3

Output

1
3 4 INF 9 1

题解

题目解法

可以把 bug 视为一个图：有一个虚拟的 0 号节点代表彻底修复的 bug。如果第 $i$ 个 bug 可以转变为 $j$ 类 bug ，则由 $j$ 连接到 $i$ 一条单向边，权重为所需时间。如果可以彻底修复第$i$类 bug，则由 $0$ 连接到 $i$ 一条单向边，权重为所需时间。然后求 $0$ 号节点到每个节点的最短路即可。

分析时间复杂度：$1 \leq N \leq 10^5$ $0 \leq K,M \leq 2*10^5$ 因此使用堆优化的 $dijkstra$ （时间复杂度为$O\left(m \times \log\left(m\right)\right)$）即可。

AC代码

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
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define MAXN 100050
struct road{
    int from;
    int time;
    road(int from, int time): from(from), time(time){}
    bool operator>(const road& that) const {
        return time > that.time;
    }
};
vector<road> roads[MAXN];
int dji[MAXN] = {0x3fffffff};
int vis[MAXN] = {0};
int n,k,m;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>k>>m;
    int t,a,b;
    for(int i = 0; i < k; ++ i){
        cin>>a>>b;
        roads[0].emplace_back(a, b);
    }
    for(int i = 0; i < m; ++ i){
        cin>>a>>b>>t;
        roads[b].emplace_back(a, t);
    }

    int count = 0;
    priority_queue<road, vector<road>, greater<road> > que;
    for(int i = 1; i <= n; ++ i){
        dji[i] = 0x3fffffff;
        vis[i] = 0;
    }
    dji[0] = 0;
    que.emplace(0,0);
    while(!que.empty()){
        int from = que.top().from;
        que.pop();
        if(vis[from]){
            continue;
        }
        vis[from] = 1;
        for(auto &rr: roads[from]){
            if (dji[rr.from] > rr.time + dji[from]){
                dji[rr.from] = rr.time + dji[from];
                que.emplace(rr.from, dji[rr.from]);
            }
        }
        count++;
        if(count == n+1) break;
    }

    for(int i = 1; i <= n; ++ i){
        if(dji[i] < 0x3fffffff){
            cout<<dji[i]<<" ";
        } else {
            cout<<"INF ";
        }
    }
    return 0;
}