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