【Codeforces 25C】Roads in Berland

题意

【题解】

用floyd思想。
求出来这条新加的边影响到的点对即可。
然后尝试更新点对之间的最短路就好。
更新之后把差值从答案里面减掉。

【代码】

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 300;

int n;

ll dis[N+10][N+10];

int k;

ll ans = 0;

void updata(ll &x,ll y){

    if (x>y){

        ans-=(x-y);

        x = y;

    }

}

int main(){

    ios::sync_with_stdio(0),cin.tie(0);

    cin >> n;

    for (int i = 1;i <= n;i++)

        for (int j = 1;j <= n;j++){

            cin >> dis[i][j];

            if (i<=j) ans += dis[i][j];

        }

    cin >> k;

    for (int i = 1;i <= k;i++){

        int x,y,z;

        cin >> x >> y >> z;

        for (int i1 = 1;i1 <= n;i1++)

            for (int i2 = 1;i2<=n;i2++){

                updata(dis[x][y],z);

                if (dis[x][y]!=dis[y][x]){

                    dis[y][x] = dis[x][y];

                }

                updata(dis[i1][i2],dis[i1][x]+dis[y][i2]+z);

                if (dis[i1][i2]!=dis[i2][i1]){

                    dis[i2][i1] = dis[i1][i2];

                }

            }

        cout<<ans<<" ";

    }

    return 0;

}

巴特西

【Codeforces 25C】Roads in Berland

最新文章

热门文章