0%

2020工大杯题解-E

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

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

题目描述

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

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

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

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

输入

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

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

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

输出

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

数据规模

对于100%的数据有:

输入输出样例

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。如果第 个 bug 可以转变为 类 bug ,则由 连接到 一条单向边,权重为所需时间。如果可以彻底修复第类 bug,则由 连接到 一条单向边,权重为所需时间。然后求 号节点到每个节点的最短路即可。

分析时间复杂度: 因此使用堆优化的 (时间复杂度为)即可。

AC代码

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

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