0%

2020工大杯题解-E

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

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

题目描述

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

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

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

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

输入

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

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

而后M行,每行三个整数BjB_jCjC_jT2jT_{2j},代表L同学掌握一种方法能够用T2jT_{2j}的时间将一个BjB_j类BUG修复,但同时会产生一个CjC_j类BUG。

输出

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

数据规模

对于100%的数据有:

1N1051 \leq N \leq 10^5

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

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

1Ai,Bj,CjN1 \leq A_i,B_j,C_j \leq N

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

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

输入输出样例

Input

5 3 4
1 3
2 9
5 1
1 3 4
4 2 5
1 2 2
2 5 3

Output

3 4 INF 9 1 

题解

题目解法

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

分析时间复杂度:1N1051 \leq N \leq 10^5 0K,M21050 \leq K,M \leq 2*10^5 因此使用堆优化的 dijkstradijkstra (时间复杂度为O(m×log(m))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<

欢迎关注我的其它发布渠道