T3-10 Rendez-vous

思路

题意简化

• Marian 从节点 $1$ 出发，Robin 从节点 $n$ 出发
• 某些节点有马，骑上后边权永久减半
• 两人可以在任意节点等待对方
• 求最早相遇时间 = $\min_v \max(d_1(v),\; d_n(v))$

分层图 Dijkstra

每个人有两种状态：有马和无马。用 $(节点, 是否有马)$ 建分层图。

状态定义：

• $d[u][0]$：到达节点 $u$，无马的最短时间
• $d[u][1]$：到达节点 $u$，有马的最短时间

转移规则：

从 $(u, s)$ 经边 $(u, v, w)$ 转移：

当前状态	→ $(v, 0)$ 无马	→ $(v, 1)$ 有马
$s = 0$（无马）	$d[u][0] + w$	若 $v$ 有马：$d[u][0] + w$
$s = 1$（有马）	—	$d[u][1] + w/2$

骑马后状态不可逆（不会下马），所以 $s=1$ 不会转移到 $s=0$。

代码

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

typedef long long ll;
typedef pair<ll, int> pli;

const ll INF = 1e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

        vector<bool> horse(n + 1, false);
        for (int i = 0; i < h; i++) {
            int x; cin >> x;
            horse[x] = true;
        }

        vector<vector<pair<int, int>>> adj(n + 1);
        for (int i = 0; i < m; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            adj[u].push_back({v, w});
            adj[v].push_back({u, w});
        }

        // 分层图 Dijkstra
        // 状态编码：node * 2 + state（0 = 无马，1 = 有马）
        auto dijkstra = [&](int src) -> vector<array<ll, 2>> {
            vector<array<ll, 2>> d(n + 1, {INF, INF});
            priority_queue<pli, vector<pli>, greater<pli>> pq;

            d[src][0] = 0;
            pq.push({0, src * 2 + 0});

            if (horse[src]) {
                d[src][1] = 0;
                pq.push({0, src * 2 + 1});
            }

            while (!pq.empty()) {
                auto [dist, code] = pq.top(); pq.pop();
                int u = code / 2, s = code % 2;

                if (dist > d[u][s]) continue;  // 过时状态，跳过

                for (auto [v, w] : adj[u]) {
                    ll cost = (s == 1) ? w / 2 : w;  // 有马则边权减半

                    // 保持当前状态转移
                    if (d[u][s] + cost < d[v][s]) {
                        d[v][s] = d[u][s] + cost;
                        pq.push({d[v][s], v * 2 + s});
                    }

                    // 无马到达有马节点 → 获得马
                    if (s == 0 && horse[v] && d[u][0] + cost < d[v][1]) {
                        d[v][1] = d[u][0] + cost;
                        pq.push({d[v][1], v * 2 + 1});
                    }
                }
            }
            return d;
        };

        auto d1 = dijkstra(1);   // Marian 从 1 出发
        auto dn = dijkstra(n);   // Robin 从 n 出发

        ll ans = INF;
        for (int v = 1; v <= n; v++) {
            ll from1 = min(d1[v][0], d1[v][1]);
            ll fromn = min(dn[v][0], dn[v][1]);
            if (from1 < INF && fromn < INF)
                ans = min(ans, max(from1, fromn));
        }

        cout << (ans >= INF ? -1 : ans) << "\n";
    }

    return 0;
}