CF1737D 题解

· · 题解

可以发现最优决策肯定是把一条边 (u_i,v_i,w_i) 一直挪到成为 (1,n)，证明考虑反证法。这样的代价是 w_i\times ([\text{挪动次数}] + 1) 的。 因此我们可以枚举边来更新答案。
问题转化成：给定一条边，求挪动次数最小值。

首先我们可以发现，挪动次数与边权无关，因此我们可以首先将原图上的边权置为 1，得到一张新图。
随后我们可以发现，一个端点 u 移动到 v 的最小移动次数是 u,v 在新图上的最短路长度。因此首先在新图上跑一遍 floyed 算法得到两点间最短路 dis(u,v)。

然后分情况讨论 (u,v) 边的挪动次数：

  1. 两点分别走到 1,n 两点。
    例：dis(u,1) + dis(v,n)

  2. 枚举中转点 j。其中一个点走到 j 点，随后让另一个点一步挪动到 j 点，再分别走到 1,n 两点。这里的中转点可以是 1/n 。
    例：dis(u,j) + 1 + dis(j,1) + dis(j,n)

预处理复杂度 O(n^3)，枚举边并判断复杂度 O(nm)。

\text{code : } 
int T, n, m, t1, t2;
ll ans;
struct {int u, v, w;} e[N];
int g[501][502];

int main() {
    get(T);
    while (T--) {
        get(n, m); rep(i,1,n) rep(j,1,n) if (i != j) g[i][j] = inf; ans = infll;
        rep(i,1,m) get(e[i].u, e[i].v, e[i].w), g[e[i].u][e[i].v] = g[e[i].v][e[i].u] = 1;
        rep(k,1,n) rep(i,1,n) rep(j,1,n) g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
        rep(i,1,m) {
            int now = min( {g[1][e[i].u] + g[e[i].v][n], g[1][e[i].v] + g[e[i].u][n]} );
            rep(j,1,n) now = min( {now, g[e[i].u][j] + 1 + g[1][j] + g[j][n], g[e[i].v][j] + 1 + g[1][j] + g[j][n]} );
            ans = min(ans, 1ll * e[i].w * (now + 1));
        } cout << ans << '\n';
    }
}