codeforces 25C. Roads in Berland

旧城等待， 2022-08-03 08:23 26阅读 0赞

有n个城市，每个城市都能到达别的城市，n\*n的矩阵表明i到j城市的最短距离，现在要建造一些新的道路，在两个城市之间。问每次建造这些道路之后每两个城市之间的距离之和为多少。

如果新建的道路比当前的最短道路要长，那么总和不会更新，如果要短的话，那么要把当前道路最短距离更新。

同时枚举其他各个城市之间的距离有没有变小。假设t1到t2之间距离更新了，对于任意两个城市i，j，要比较一下从i到j的最短距离是不是比

从i到t1，再从t1到t2，再从t2到j的距离和大，，大的话就更新。注意没说最短距离的范围，要用long long

#include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    int maze[333][333];
    int main()
    {
        int n=in();
        ll ans=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                maze[i][j]=in();
                ans+=maze[i][j];
            }
        }
        ans>>=1;
        int k=in();
        for(int ii=0;ii<k;ii++)
        {
            int t1=in(),t2=in(),t3=in();
            if(t3>=maze[t1][t2])
            {
                printf("%I64d\n",ans);
                continue;
            }
            ll cnt=maze[t1][t2]-t3;
            maze[t1][t2]=t3;
            maze[t2][t1]=t3;
    
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    if(maze[i][j]>maze[i][t1]+maze[t1][t2]+maze[t2][j])
                    {
                        cnt+=maze[i][j]-maze[i][t1]-maze[t1][t2]-maze[t2][j];
                        maze[i][j]=maze[i][t1]+maze[t1][t2]+maze[t2][j];
                        maze[j][i]=maze[i][j];
                    }
                }
            }
            ans-=cnt;
            printf("%I64d ",ans);
        }
        return 0;
    }