1 条题解

  • 0
    @ 2025-3-12 14:37:43
    #include <bits/stdc++.h>
    #define int long long
    using namespace std;
    const int MAXN = 10000;
    const int INF = 2147483647;
    int n, m, b;     // 城市数量,公路数量,血量
    int f[MAXN + 5]; // 每个城市过路费
    // 存图 <终点,血量花费>
    vector<pair<int, int>> e[MAXN + 5];
    
    // 检查花费最大值小于等于 mid 时能否达成
    int dis[MAXN + 5]; // 最少花费血量
    bool vis[MAXN + 5];
    // <花费血量,城市编号>
    priority_queue<pair<int, int>> pq;
    bool check(int mid)
    {
        if (f[1] > mid)
            return false;
        for (int i = 1; i <= n; i++)
        {
            dis[i] = INF;
            vis[i] = false;
        }
        dis[1] = 0;
        pq.push(make_pair(-0, 1));
        while (!pq.empty())
        {
            int u = pq.top().second;
            pq.pop();
            if (vis[u])
                continue;
            vis[u] = true;
            for (int i = 0; i < e[u].size(); i++)
            {
                int v = e[u][i].first;
                int w = e[u][i].second;
                if (f[v] <= mid && dis[u] + w < dis[v])
                {
                    dis[v] = dis[u] + w;
                    pq.push(make_pair(-dis[v], v));
                }
            }
        }
        return dis[n] <= b;
    }
    
    signed main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> n >> m >> b;
        for (int i = 1; i <= n; i++)
            cin >> f[i];
        for (int i = 1; i <= m; i++)
        {
            int u, v, w;
            cin >> u >> v >> w;
            e[u].push_back(make_pair(v, w));
            e[v].push_back(make_pair(u, w));
        }
    
        // 二分限制花费的最大值
        int l = 0;
        int r = 1'000'000'000;
        int ans = -1;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (check(mid))
            {
                ans = mid;
                r = mid - 1;
            }
            else
            {
                l = mid + 1;
            }
        }
    
        if (ans == -1)
            cout << "AFK";
        else
            cout << ans;
        return 0;
    }
    
    • 1

    信息

    ID
    1830
    时间
    1000ms
    内存
    128MiB
    难度
    4
    标签
    递交数
    52
    已通过
    7
    上传者