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

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

Output

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代码

#include 
#include 
#include 
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 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, greater > 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<