湖南省赛

K题

题意

你可以免费移动经过一条边，求在满足在任意点开始都能成功渡劫的最小花费。

思路

1. 建一个虚拟源点，连向每一个点，将这条边的边权设为这个点渡劫需要的花费。
2. 跑最短路，这样会把每一种情况囊括在内，但是没有考虑免费的移动。
3. 建一个 dist2 数组，用来记录每一个点当前真正的最小花费（已用免费次数），类似状态转移。
4. 每一次对 dist1[u]，dist2[v] + w 和本身取 min 进行更新。
5. 最后遍历 dist2 数组取 max 即为答案。

代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    #define int long long
    
    int n, m;
    cin >> n >> m;
    
    vector<vector<pair<int, int>>> g(n + 1);
    int INF = 2e18;
    vector<int> dist1(n + 1, INF), dist2(n + 1, INF);
    
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].emplace_back(b, c);
        g[b].emplace_back(a, c);
    }
    
    vector<int> a(n + 1);
    int minn = INF;
    int st = 0;
    
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        dist2[i] = a[i]; // 初始化
    }
    
    for (int i = 1; i <= n; i++) {
        g[0].emplace_back(i, a[i]);
    }
    
    vector<int> f(n + 1);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> heap;
    dist1[st] = 0;
    dist2[st] = 0; // dist1 记录不用，dist2 记录用免费的，也就是当前最小
    int ans = 0; // 要取 max
    
    heap.emplace(dist1[st], st);
    
    while (heap.size()) {
        auto [d, u] = heap.top();
        heap.pop();
        
        if (f[u]) continue;
        f[u] = 1;
        
        for (auto [v, w] : g[u]) {
            if (dist1[v] > dist1[u] + w) { // 算出到上一个的消耗
                f[u] = 0;
                dist1[v] = min({dist1[u] + w, dist1[v]});
                heap.emplace(dist1[v], v);
            }
            if (u) dist2[v] = min({dist1[u], dist2[u] + w, dist2[v]}); // 更新每个点的最小能量
        }
    }
    
    for (int i = 1; i <= n; i++) {
        ans = max(ans, dist2[i]);
    }
    
    cout << ans << '\n';
}