北大ACM队的远足

题面

给定一张 N 个点 M 条边的有向无环图，点的编号从 0 到 N - 1，每条边都有一个长度。

给定一个起点 S 和一个终点 T。

若从 S 到 T 的每条路径都经过某条边，则称这条边是有向图的必经边或桥。

北大 ACM 队要从 S 点到 T 点。

他们在路上可以搭乘两次车。

每次可以从任意位置（甚至是一条边上的任意位置）上车，从任意位置下车，但连续乘坐的长度不能超过 q 米。

除去这两次乘车外，剩下的路段步行。

定义从 S 到 T 的路径的危险程度等于步行经过的桥上路段的长度之和。

求从 S 到 T 的最小危险程度是多少。

输入格式

第一行包含整数 L，表示共有 L 组测试数据。

每组测试数据，第一行包含五个整数 N,M,S,T,q 。

接下来 M 行，每行包含三个整数u,v,w，表示点 u 到点 v 存在一条边，长度为 w。

输出格式

每组数据输出一个结果，每个结果占一行。

若没有从 S 到 T 的路径，则输出 -1。

数据范围

1≤L≤5,
1≤N≤105,
1≤M≤2∗105,
0≤S,T<N,S≠T,
1≤q≤109,
1≤w≤1000

输入样例：

输出样例：

题解

错的细节, 这是区间覆盖题, 不是找两个最长的桥
对于有向图, 必须是入度为0的节点入队, 你把 st 入度, dfs的可能会因为有的点还有 deg 而无法入队

先说一下增么求割点割边, 求割边的话有 nlogn 的Lengauer-Tarjan, 再去求割点

但是, lydnb, 给了个 O(n) 的算法

fs[i] 表示 start 到 i 的线路总数
ft[i] 表示 end   到 i 的线路总数

那么 fs[x] * ft[x] == fs[ed] x是割点
    fs[x] * ft[y] == fs[ed] (x, y)是割边

然而! __int128都不一定能存下那么多的方案数, 所以我们要用hash
怕被卡的, 可以用fs[i][k], 每一个fs[i][j] 对应一个模数 mod[j], 当所有hash值都满足的时候  上式成立

然后是区间覆盖, 你求出路径后, 就可以转成dp问题了

一堆点横着排, 相邻的点有个距离, 有的点相邻之间是桥, 让你求 start~end, 你走过的桥的最短距离

期间你可以在任意地方上车, 最多乘坐q米, 能坐两次

乘车区间肯定可以使得左顶点或右顶点 正好在一个点上
1.乘车区间只有一个桥, 显然你可以平移使得成立
2.左端在桥区间里, 中间有不是桥的路径, 右端也在桥的区间里, 显然你也可以平移, 使得端点有一端卡这一个节点

即要么你在一个点上车, 要么你在一个点下车

显然的线性dp了, 找个点, 把路径隔开, 左边的是在节点下车, 右边的是在节点上车, 这样拼接正好不重复

还有一种最特殊的情况有个桥长到, 可以从节点上车在桥中间下车再次上车, 或者在此桥前面上车, 桥中间下车再上车, 到节点下车

一共就这两种方式, 细节看代码(这是板子改的, 有些代码用不到可以删了)

#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef double db;

const int N = 1e5 + 5, M = 2e5 + 5;
const int mod = 999983;

int n, m, _, k;
int h[N], ne[M], to[M], co[M], tot;
int ph[N], pn[M], pt[M];
int indeg[N], outdeg[N], pre[N];
int st, ed, q;
ll fs[N], ft[N], dis[N];
bool cut[N], edge[M];
VI path;

int ds[N], dt[N], g[N << 1], d[N << 1];
bool bri[M];

void add(int u, int v, int c) {
    ne[++tot] = h[u]; to[h[u] = tot] = v; co[tot] = c;
    pn[tot] = ph[v]; pt[ph[v] = tot] = u;
}

void topsort(int s, int h[], int ne[], int to[], ll f[], int deg[]) {
    queue<int> q; f[s] = 1;
    rep (i, 1, n) if (!deg[i]) q.push(i);
    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int i = h[x]; i; i = ne[i]) {
            int y = to[i], w = co[i];
            if (s == st && dis[y] > dis[x] + w) dis[y] = dis[x] + w, pre[y] = i;
            f[y] = (f[y] + f[x]) % mod;
            if (!--deg[y]) q.push(y);
        }
    }
}

void findcut() {
    rep(i, 1, n) cut[i] = fs[i] * ft[i] % mod == fs[ed];
}

void findedge() {
    rep(i, 1, tot) {
        int x = pt[i], y = to[i];
        edge[i] = fs[x] * ft[y] % mod == fs[ed];
    }
}

void getpath() {
    VI(1, ed).swap(path);
    for (int i = pre[ed]; to[i]; i = pre[pt[i]]) 
        path.pb(pt[i]);
    reverse(all(path));
}

void solve() {
    getpath();
    per(i, path.size(), 1) d[i] = dis[path[i - 1]];
    rep(i, 2, path.size())
        bri[i] = edge[pre[path[i - 1]]], g[i] = g[i - 1] + (bri[i] ? co[pre[path[i - 1]]] : 0);

    int k = 1;
    rep(i, 2, path.size()) {
        ds[i] = min(g[i], ds[i - 1] + g[i] - g[i - 1]);
        while (k < i && d[i] - d[k] > q) ++k;
        ds[i] = min(ds[i], g[k] - (bri[k] ? q - d[i] + d[k] : 0));
    }

    dt[k = path.size()] = 0;
    per(i, path.size() - 1, 1) {
        dt[i] = min(g[path.size()] - g[i], dt[i + 1] + g[i + 1] - g[i]);
        while (k > i && d[k] - d[i] > q) --k;
        dt[i] = min(dt[i], g[path.size()] - g[k] - (bri[k + 1] ? q - d[k] + d[i] : 0));
    }

    int ans = 2e9;
    rep(i, 1, path.size()) ans = min(ans, ds[i] + dt[i]);
    k = 1;
    rep(i, 2, path.size()) {
        while (k < i && d[i] - d[k] > 2 * q) ++k;
        ans = min(ans, g[path.size()] - g[i] + g[k] - (bri[k] ? 2 * q - d[i] + d[k] : 0));
    }
    cout << ans << '
';
}

int main() {
    IOS;
    for (cin >> _; _; --_) {
        cin >> n >> m >> st >> ed >> q; tot = 0; ++st, ++ed;
        rep(i, 1, n) {
            ph[i] = h[i] = indeg[i] = outdeg[i] = pre[i] = 0;
            cut[i] = fs[i] = ft[i] = 0; dis[i] = 2e9;
        }
        dis[st] = 0;
        rep(i, 1, m) {
            int u, v, c; cin >> u >> v >> c;
            add(++u, ++v, c); ++indeg[v], ++outdeg[u];
        }
        topsort(st, h, ne, to, fs, indeg);
        if (dis[ed] == 2e9) { cout << -1 << '
'; continue; }
        topsort(ed, ph, pn, pt, ft, outdeg);
        findedge();
        solve();
    }
    return 0;
}