# 【題解】JOI18 commuter pass

## 題意

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

## 作法

將無向圖拆成有向圖，可以得到 $stDAG$ 的任何完整路徑（從入度為零的點開始，走到出度為零的點為止）都是 $s-t$ 最短路。

$u-v$ 最短路有兩種可能：

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$。此時的前驅 $i$ 就會是 $y$，後繼 $j$ 就會是 $x$，套用前面方法求 $ans$ 即可。

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

## AC Code

#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';
}