OiClass TIGAO P3333 路径难题题解

思路

首先考虑暴力建边的做法，我们使用 \(\mathcal{O}({t_i}^2)\) 的时间建立公交站的边。然后我们考虑如何计算答案。考虑到每次坐公交车的时候都会进行出租车的结算，于是我们直接累计到最后才向上取整的做法是没有正确性的。

于是我们考虑每次到公交节点的时候就进行向上取整，这样就可以保证 Dijkstra 的正确性。

这样就解决了正确性的问题，然后考虑如何优化公交的建边。我们可以采用常用的套路：虚点。通过建立一个和所有公交站点连线的虚点来表示一个公交站。其中，向虚点的“上车”路线代价是 \(c\)，下车的从虚点到站点的代价是 \(0\)。这样就解决的建边时间复杂度的问题。

给予上面的思路简单实现即可。

代码

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>

#define int long long
#define endl '\n'

using namespace std;

int n, m, k, r, q;
double dis[200009];
vector<pair<int, double>> g[200009];

void dijkstra(int s) {
    priority_queue<pair<double, int>> pq;
    pq.push({0, s});
    memset(dis, 127, sizeof(dis));
    dis[s] = 0;
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        for (auto [v, w] : g[u]) {
            if (dis[v] > dis[u] + w) {
                if (v > n) {
                    dis[v] = ceil(dis[u] + w);
                } else {
                    dis[v] = dis[u] + w;
                }
                pq.push({-dis[v], v});
            }
        }
    }
}

signed main() {
    freopen("path.in", "rt", stdin);
    freopen("path.out","wt", stdout);
    cin >> n >> m >> k >> r >> q;
    for (int u, v, w, i = 1; i <= m; i++) {
        cin >> u >> v >> w;
        g[u].push_back({v, w * 1.0 / r});
        g[v].push_back({u, w * 1.0 / r});
    }
    for (int i = 1, t, c; i <= k; i++) {
        cin >> t >> c;
        for (int j = 1, x; j <= t; j++) {
            cin >> x;
            g[n + i].push_back({x, 0});
            g[x].push_back({n + i, c});
        }
    }
    for (int i = 1, u, v; i <= q; i++) {
        cin >> u >> v;
        dijkstra(u);
        cerr << endl;
        cout << (int) ceil(dis[v]) << endl;
    }
}