P6464 传送门

已知全源最短路后枚举一条新增边

问题

P6464 [传智杯 #2 决赛] 传送门
给定一张连通无向正权图，可以选择两个教学楼建立一对传送门，使它们之间的距离变为零。需要选择最优端点，使加入传送门后所有无序点对最短路之和最小，每一对点只统计一次。

数据规模：$n\le100$，$m\le\frac{n(n-1)}2$，边权满足 $1\le w_i\le10^4$，图中无自环和重边。

所有点对之间的最短路之和，观察数据规模，不难想到使用 Floyd 全源最短路。

但是如何考虑新加入的传送门呢？数据规模很小暗示我们可以直接暴力枚举每一条边。

假设对 $(u,v)$ 加入一条零权边，任意点对的最短路都有可能发生变化。不过只要它发生变化，新路径就一定经过这条传送边；传送门两侧的路段仍可直接使用原图的全源最短路。

也就是说，任意点对 $x, y$ 的新距离要么是原距离，要么是 $x \to u \to v \to y$，要么是 $x \to v \to u \to y$。于是只需要先对原图跑一次 Floyd，然后再在暴力枚举新边的同时，累计最短路之和即可。

▶

P6464

ll dis[maxn][maxn];

void solve( ) {
    int n = read( ), m = read( );

    for( int i = 1; i <= n; ++ i ) {
        for( int j = 1; j <= n; ++ j ) {
            dis[i][j] = i == j ? 0 : inf;
        }
    }
       
    for( int i = 1; i <= m; ++ i ) {
        int u = read( ), v = read( );
        ll w = read( );
        dis[u][v] = dis[v][u] = min( dis[u][v], w );
    }

    for( int k = 1; k <= n; ++ k ) {
        for( int i = 1; i <= n; ++ i ) {
            for( int j = 1; j <= n; ++ j ) {
                dis[i][j] = min( dis[i][j], dis[i][k] + dis[k][j] );
            }
        }
    }

    ll ans = inf;
    for( int u = 1; u <= n; ++ u ) {
        for( int v = u + 1; v <= n; ++ v ) {
            ll res = 0;
            for( int x = 1; x <= n; ++ x ) {
                for( int y = x + 1; y <= n; ++ y ) {
                    ll d = dis[x][y];
                    d = min( d, dis[x][u] + dis[v][y] );
                    d = min( d, dis[x][v] + dis[u][y] );
                    res += d;
                }
            }
            ans = min( ans, res );
        }
    }
    printf( "%lld\n", ans );
}