codeforces 25C. Roads in Berland-蒲公英云

codeforces 25C. Roads in Berland

有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;
}