题解 | D. 水群

D. 水群

如图所示，我们需要从 走到 （图中 ）

两种不同的边对应不同代价，由于这个图不是 DAG，不能直接

可以直接套最短路 Dijkstra 解决

代码如下

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define fType int
#define foreach(x, a, b) for (fType x = a, _end_ = b; x <= _end_; x++)
#define foreach_sub(x, a, b) for (fType x = a, _end_ = b; x >= _end_; x--)
#define tpl make_tuple

const ll INF = 1000000000000000000ll;
using pr = pair<ll, int>;
void Dijkstra(int s, int n, vector<ll> &dis, vector<vector<pr>> &gp)
{
    dis.assign(n + 1, INF);
    vector<bool> vis(n + 1);
    priority_queue<pr, vector<pr>, greater<pr>> pq;

    pq.push({dis[s] = 0, s});

    while (!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();

        if (vis[u]) continue;
        vis[u] = 1;

        for (auto &[w, v] : gp[u])
            if (dis[u] + w < dis[v]) pq.push({dis[v] = dis[u] + w, v});
    }
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    int _;
    cin >> _;

    while (_--)
    {
        int n, m;
        cin >> n >> m;

        ll x, y;
        cin >> x >> y;

        vector<vector<pr>> gp(n + 1);
        foreach (i, 1, m)
        {
            int u, v;
            cin >> u >> v;
            gp[v].emplace_back(y, u);
        }

        foreach (i, 1, n - 1)
        {
            gp[i].emplace_back(x, i + 1);
            gp[i + 1].emplace_back(x, i);
        }

        vector<ll> dis;
        Dijkstra(1, n, dis, gp);

        cout << dis[n] << "\n";
    }

    return 0;
}

扩展思考：如果 ，能不能更快解决这个问题呢？