Dytechlab Cup 2022(div1+div2) D.Ela and the Wiring Wizard

题意

给定一个无向图，现在有操作：假设点u,v直接相连，边权为w，t与v直接相连，那么可以把u，v之间的边与v断开，连到t上，于是现在t-u多了一条权值为w的边。

每次操作的贡献为边权大小。在任意多次操作的条件下，求从点1到点n的最短路。

思路

首先，贪心考虑是否操作后的最短路比原图的短。假设原图的最短路的权为s，最短路上的边数为m（即1到n之间的边数），在最短路上选取权值为w的最小的一个边，发现只需要m-1次操作就能把1和n连起来，此时最短路为w*(m-1)+w，而s>=m*w，所以比原图优。

在这个前提下，肯定要操作某条边，把1和n连接起来，最优的情况一定在这里面。假设dist[i][j]为点i与点j之间最少的边数，g[i][j]为连接i与j的边的边权。于是枚举每一条边，分两种情况：

1.该边在1-n的路径之中（注意不是必须为最短路），那么操作后的路径权值为g[i][j]*(dist[1][i]+dist[j][n]+1)，注意i与j的顺序不重要，因为枚举的时候i与j会互换。

2.该边不在1-n的路径之中。那么此时需要枚举1-n之间经过的路径，假设该路经过点k，然后把i-j这条边转移到点k上，需要dist[i][k]次操作（注意j也行，因为迟早互换）。然后再来一次操作把这条边变成点k处的自环（这样才能把这条边加入路径），然后就进行dist[1][k]+dist[k][n]次操作。总权值为g[i][j]*(dist[i][k]+1+dist[1][k]+dist[k][n]+1)。

时间复杂度(o^3)

代码：

 1 #include<iostream>
 2 #include<string>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<stack>
 6 #include<queue>
 7 #include<map>
 8 #include<vector>
 9 using namespace std;
10 typedef long long LL;
11 #define INF 1e18
12 #define endl '\n'
13 const int N = 5e2 + 10;
14 LL g[N][N], dist[N][N];
15 int n, m;
16 void floyd()
17 {
18     for (int k = 1; k <= n; k++)
19         for (int i = 1; i <= n; i++)
20             for (int j = 1; j <= n; j++)
21                 dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j]);
22 
23 
24 
25 }
26 void solve()
27 {
28     
29     cin >> n >> m;
30     for (int i = 1; i <= n; i++)
31         for (int j = 1; j <= n; j++)
32             g[i][j] = dist[i][j] = INF;
33     for (int i = 1; i <= n; i++)g[i][i] = dist[i][i] = 0;
34     while (m--)
35     {
36         LL u, v, w;
37         cin >> u >> v >> w;
38         g[u][v] = g[v][u] = min(g[u][v], w);
39         dist[u][v] = dist[v][u] = 1;
40     }
41     floyd();//把每条边边权看为1，那么floyd能求出dist[i][j].
42 
43     LL ans = INF;
44     for(int i=1;i<=n;i++)
45         for (int j = 1; j <= n; j++)
46         {
47             //边不存在
48             if (i == j||g[i][j]==INF)continue;
49             //边i-j在路径上
50             ans = min(ans, g[i][j] * (1 + dist[1][i] + dist[j][n]));
51             //边i-j不在路径上
52             for (int k = 1; k <= n; k++)
53                 ans = min(ans, g[i][j] * (dist[i][k] + 1 + dist[1][k] + dist[k][n] + 1));
54         }
55     cout << ans << endl;
56 }
57 int main()
58 {
59     ios::sync_with_stdio(false);
60     cin.tie(0);
61     cout.tie(0);
62     int T;
63     cin >> T;
64     while (T--)
65         solve();
66 
67     return 0;
68 }