總有一天會用到的筆記

本站為減緩筆者下列疑難雜症誕生：記性很差，學過就忘；智商低落，囫圇吞棗。

0%

【題解】JOI18. Commuter Pass

發表於 分類於

JOI18. Commuter Pass

有 \(n\) 點 \(m\) 邊的帶權無向圖（\(n\le 10^5; m \le 2\times10^5\)）。你可以指定一條 \(s-t\) 的最短路使其邊權歸零，求 \(u-v\) 的最短路徑。

作法

考慮將無向圖拆成有向圖。存在 \(stDAG\) 的任何完整路徑（從入度為零的點開始，走到出度為零的點為止）都是 \(s-t\) 最短路。

答案有三種可能：

  1. 不經過 \(s-t\) 最短路，\(ans = dis(u,v)\)
  2. \(u\) 從 \(x\) 接入 \(stDAG\)，從 \(y\) 離開 \(stDAG\) 前往 \(v\)，\(ans = dis(u,x)+dis(y,v)\)
  3. \(v\) 從 \(x\) 接入 \(stDAG\)，從 \(y\) 離開 \(stDAG\) 前往 \(u\)，\(ans = dis(v,x)+dis(y,u)\)

想找出 \(dis(v,x)\) 和 \(dis(y,u)\) 只要從 \(u,v\) 分別作 Dijkstra 即可。

如何找到 \(x, y\) ?

考慮在 \(stDAG\) 上 DP：

  • \(dpu[i]\) 代表 \(path(s,i)\) 上最小的 \(dis(u,i)\)
  • \(dpv[i]\) 代表 \(path(s,i)\) 上最小的 \(dis(v,i)\)

則將 \(i\) 作為 \(y\) 的答案即為 \(min(dpu[prev]+dis(v,i), dpv[prev]+dis(u,i))\)。

如何在 \(stDAG\) 上 DP？

對於正邊權圖，只要維護 \(vis\) 使得每個點只會被拿出來一次，Dijkstra 拿出來的順序就是在單源最短路 DAG 上的拓樸排序。

因此我們可以從 \(s\) 做一次 Dijkstra ，在 \(sDAG\) 上得到 \(dpu\) 和 \(dpv\)。

若我們在 \(sDAG\) 的反圖 \(sDAG'\) 上從 \(t\) 做 BFS 相當於在 \(tsDAG\) BFS。此時任一節點 \(i\)，後繼節點為 \(j\)，則將 \(i\) 作為 \(y\) 的答案是 \(min(dpu[j]+dis(v,i), dpv[j]+dis(u,i))\)

BFS 不用另外寫，直接重複使用 Dijkstra 即可（被拿出來的順序不重要）。

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>
#define int long long
#define rep(i,j,k) for (int i=j; i<=k; i++)
#define pb push_back
#define lyx_my_wife ios::sync_with_stdio(0), cin.tie(0);
using namespace std;
typedef pair<int,int> pii;
 
const int N = 1e5+10, M = 2e5+10;
 
int n, m, s, t, u, v;
vector<pii> G[N];
 
int disu[N], disv[N], diss[N], dist[N], vis[N];
int dpu[N], dpv[N], ans;
 
void dijks(int rt, int dis[N], int fordp=0, int forans=0)
{
    memset(dis, 0x3f, sizeof(disu));
    memset(vis, 0, sizeof(vis));
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    dis[rt] = 0;
    pq.push({0, rt});
 
    if (fordp)
    {
        memset(dpu, 0x3f, sizeof(dpu));
        memset(dpv, 0x3f, sizeof(dpv));
    }
    
    while(pq.size())
    {
        int i = pq.top().ss, d = pq.top().ff;
        pq.pop(); 
 
        if (vis[i]) continue;
        vis[i] = 1;
 
        if (fordp)
        {
            dpu[i] = min(dpu[i], disu[i]);
            dpv[i] = min(dpv[i], disv[i]);            
        }
 
        for (auto e: G[i])
        {
            int j = e.ss, w = e.ff;
 
            if (forans)
            {
                if (diss[j] != diss[i]-w) continue;
                ans = min(ans, dpu[j]+disv[i]);
                ans = min(ans, dpv[j]+disu[i]);
            }
 
            if (dis[j] > d+w)
            {
                dis[j] = d+w;
                pq.push({dis[j], j});
                if (fordp) dpu[j] = dpu[i], dpv[j] = dpv[i];
            }
            else if (dis[j] == d+w)
            {
                if (fordp) dpu[j] = min(dpu[j], dpu[i]), dpv[j] = min(dpv[j], dpv[i]);
            }
        }
    }
}
 
signed main()
{
    lyx_my_wife
    cin >> n >> m >> s >> t >> u >> v;
    rep(_,1,m)
    {
        int i, j, w;
        cin >> i >> j >> w;
        G[i].pb({w,j});
        G[j].pb({w,i});
    }
 
    dijks(u,disu);
    dijks(v,disv);
    dijks(s,diss,1);
    ans = disu[v];
    dijks(t,dist,0,1);
    cout << ans << '\n';
}