D. Ela and the Wiring Wizard floyd/思维

Problem D
很巧妙的思维题

题意

给你一张 $n(n\le 500)$ 个点，$m(m\le 2.5e5)$ 条带权无向边的图。你的目标是从 1 走到 n。
你可以进行如下操作任意次：

1. 对于边 $(u,v,w)$ ，你可以任意选择一个与 $u$ 点间存在边的点 $t$ （$t$ 可以等于 $u$ ，即可以自环） ，花费 $w$ 时间将原边更改为 $(u,t,w)$ 。即将与 $v$ 相连改为与 $t$ 相连。

问：从 1 到 $n$ 的最短时间，时间 = 修改边花费的时间 + 最终从 1 走到 $n$ 的路径长度。

思路

假设我们现在已经通过进行若干次操作，找到了最优解对应的最后的图。那么这个路径一定满足以下条件：

1. $1$ 到 $n$ 的路径上的每条边权值相同。
2. 在上述结论的基础上，我们可以将这些边合成为 1 $\to n$ 的一条边。

证明：对于1，假设某个点连接的两条边权值不同，我们可以通过一次操作将其合并成一条边，权值为 $min(w_1,w_2)\times 2$ ，因此一定相同。条件2也类似，把 $k$ 条权值为 $w$ 的边合并成 $1$ 条边与不合并花费相同。
于是猜测最终答案可能和路径上边的数量以及路径上最短路长度有关。（因为长的边可以被短的替代）
首先我们用 floyd 算法求出任意两点间最少经过多少条边，然后可以枚举每条边是否是最终的 $w$ 。
考虑如何从 $1\to n$ ，有两种方式

1. 对于 $(u,v,w)$ ，如果 $u$ 可达 $1$ ，$v$ 可达 $n$ ，那么可以通过 $1\to u\to v\to n$
   到达。$u,v$ 互换也类似。
2. 第二种比较难想，对于边 $(u,v,w)$ ，该边先通过操作到达了某个点 $i$ 完成了一个自环，形成自环的操作数等于该边到这个点的最短距离+1，最终路径是 $1\to i\to n$ ，然后 $i$ 上的这个自环扩增的操作数为1 + $i$ 到 $1$ 和 $i$ 到 $n$ 的距离，通过枚举 $i=1\to n$ 即可。

代码

int n, m;
int f[N][N];
int u[maxm], v[maxm], w[maxm];
void solve() {
	cin >> n >> m;
	for(int i = 1; i <= m; i++) {
		cin >> u[i] >> v[i] >> w[i];
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			f[i][j] = n + 1;
		}
		f[i][i] = 0;
	}
	for(int i = 1; i <= m; i++) {
		f[u[i]][v[i]] = f[v[i]][u[i]] = 1;
	}
	for(int k = 1; k <= n; k++) {
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
			}
		}
	}
	ll ans = 2e18;
	for(int i = 1; i <= m; i++) {
		ans = min(ans, 1ll * w[i] * (f[1][u[i]]+f[v[i]][n] + 1));
		ans = min(ans, 1ll * w[i] * (f[1][v[i]]+f[u[i]][n] + 1));
		for(int k = 1; k <= n; k++) {
			ans = min(ans, 1ll * w[i] * (f[v[i]][k]+1+f[k][1]+f[k][n]+1));
			ans = min(ans, 1ll * w[i] * (f[u[i]][k]+1+f[k][1]+f[k][n]+1));
		}
	}
	cout << ans << endl;
}