2020工大杯题解-E

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

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

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

题目描述

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

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

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

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

输入

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

而后K行，每行两个整数Ai、T1i，代表L同学掌握一种方法能够用T1i的时间彻底修复一个Ai类BUG。

而后M行，每行三个整数Bj、Cj、T2j，代表L同学掌握一种方法能够用T2j的时间将一个Bj类BUG修复，但同时会产生一个Cj类BUG。

输出

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

数据规模

对于100%的数据有：

1≤N≤105

0≤K,M≤2∗105

0≤K+M≤2∗105

1≤Ai,Bj,Cj≤N

1≤T1i,T2j≤104

1≤∑i=1KT1i+∑j=1MT2j≤109

输入输出样例

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≤N≤105 0≤K,M≤2∗105因此使用堆优化的dijkstra （时间复杂度为O(m×log⁡(m))）即可。

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;
}