CF1737D Ela and the Wiring Wizard 题解

题意：

Ela 需要通过机器网络，从机器 $1$ 发送一个大型包裹到机器 $n$。目前，由于网络条件不好，她抱怨网络太慢，包裹无法及时到达。幸运的是，一位电线向导向她伸出了援手，~~据说叫cxy~~。

网络可以用一个无向连通图表示，其中有 $n$ 个节点，每个节点代表一台机器。用 $m$ 条电线连接它们。第 $i$ 条电线用于连接机器 $u_i$ 和 $v_i$，并具有权重 $w_i$。如果大型包裹经过第 $i$ 条电线，则会在恰好 $w_i$ 微秒内从机器 $u_i$ 移动到机器 $v_i$（或反之亦然）。电线向导可以随意使用她的魔法，对于每个魔法，她将选择连接机器 $u_i$ 和 $v_i$ 的第 $i$ 条电线，并按照以下步骤重新布线：

选择一个与此电线连接的机器。不失一般性，假设我们选择 $v_i$。

选择一个当前连接到 $v_i$ 的机器（包括 $u_i$），称之为 $t_i$。断开编号为 $i$ 的电线与 $v_i$ 的连接，然后使用它连接 $u_i$ 和 $t_i$。

重布线电线 $i$ 需要 $w_i$ 微秒，且重布线后电线的权重不变。重布线后，某个机器可能会有一些电线连接到自己。此外，电线向导已经警告 Ela，重新布线可能会导致一些机器之间的临时断开连接，但 Ela 无论如何都忽略了这一点。她的任务是尽可能快地将大型包裹从机器 $1$ 送到机器 $n$。请注意，巫师可以在电线上使用她的魔法零次、一次或多次。为确保在传输大型包裹时网络无缝工作，一旦包裹从机器 $1$ 开始传输，电线向导就不能再使用她的魔法移动电线。

Ela 想知道，在电线向导的帮助下，将大型包裹从机器 $1$ 传输到 $n$ 所需的最短时间是多少。

输入格式：

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1\le t\le 100$)。

测试用例的描述如下。

第一行包含 $n$ 和 $m$ ($2\le n\le 500$, $n-1\le m\le 250000$)，节点数和边数。

接下来的 $m$ 行，第 $i$ 行包含 $u_i$、$v_i$ 和 $w_i$ ($1\le u_i,v_i\le n$, $1\le w_i\le 10^9$)，表示第 $i$ 条边连接的两个节点和边的权重。

保证所有测试用例的 $n$ 总和不超过 $500$，$m$ 总和不超过 $250000$。每个测试用例中的图保证连通，无自环，但可能包含多重边。

输出格式：

对于每个测试用例，输出一个整数，表示从机器 $1$ 到 $n$ 传输大型包裹所需的最短时间。

简化题意：

有一个包含 $n$ 个点和 $m$ 条边的无向图，每条边 $i$ 连接着点 $u_i$ 和 $v_i$，权值为 $w_i$，通过这条边要用 $w_i$ 微秒。

Ela 需要从 $1$ 号点走到 $n$ 号点，但她觉得原本的路径太长了。好在，可爱的 cxy 可以帮她改变路径。

具体地，对于任意三点 $u,v,t$（$u$ 和 $t$ 可以相同），若 $u$ 与 $v$ 之间有边 $i$，且 $v$ 与 $t$ 有边 $j$，那么她可以用 $w_i$ 微秒断开边 $i$，并且在 $u$ 与 $t$ 之间连一条权值为 $w_i$ 的边。她可以改任意条边，也可以不改。

Ela 想知道，她至少要花多久时间才能从 $1$ 号点走到 $n$ 号点（时间包括修改边的时间）。

有 $t$ 组数据。

$1\le t\le 100$

$2\le n\le 500,~n-1\le m\le 250000$

$1\le u_i,v_i\le n,~1\le w_i\le 10^9$

$\sum{n}\le 500,~\sum{m}\le 250000$

保证输入的图为联通图，无自环，但可能有重边。

比较好的一道题。一开始可能会想到用 Floyd 维护某些东西。

但是样例三其实暗示了我们，很有可能全程我们只用了一条边，并把它变成边 $(1,n)$ 。

考虑反证法证明：如果最优方案用了超过一条边，则这条路径上一定存在一条更短的边，直接用最短的即可。

那么问题就很简单了，因为怎么移动边与边权无关，所以我们先 Floyd 一下得到边权为 $1$ 的最短路。

然后枚举每条边 $(u,v)$ ，计算它变成 $(1,n)$ 的花费。转移如下：

如果 $(u,v)$ 恰好在 $1 \leadsto n$ 的某条路径上，则
$\mathrm{Ans} \operatorname{\big\downarrow} \min\{d(1,u) + d(v,n), ~d(1,v) + d(u,n)\}$
否则考虑考虑让一个点走到中转点 $j$ ，然后把另一个点连向 $j$ （形成自环），接着直接移动就好了
$\mathrm{Ans} \operatorname{\big\downarrow} \min\{d(u,j),~d(v,j)\} + 1 + d(1,j) + d(j,n)$

时间复杂度 $\mathcal{O}(n^3 + nm)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x7f7f7f7f
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(515))
#define M ((int)(3e5 + 15))

int n,m,res,g[N][N];
tuple<int,int,int> e[M];
void clear()
{
    res = 0x7f7f7f7f7f7f7f7f;
    rep(i,1,n) rep(j,1,n) {
        if(i != j) g[i][j] = INF;
    }
}
void solve()
{
    cin >> n >> m; clear(); 
    for(int i = 1, u,v,w; i <= m; i++) {
        cin >> u >> v >> w; g[u][v] = g[v][u] = 1; e[i] = {u,v,w};
    }
    rep(k,1,n) rep(i,1,n) rep(j,1,n) {
        down(g[i][j], g[i][k] + g[k][j]);
    }
    for(int i = 1,u,v,w; i <= m; i++)
    {
        u = get<0>(e[i]), v = get<1>(e[i]), w = get<2>(e[i]);
        int now = min(g[1][u] + g[v][n], g[1][v] + g[u][n]);
        for(int j = 1; j <= n; j++) {
            down(now, min(g[u][j], g[v][j]) + 1 + g[1][j] + g[j][n]);
        }
        down(res, w * (now + 1));
    }
    cout << res << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q; cin >> Q; while(Q--) solve();
    return 0;
}