25C Roads in Berland Codeforces Solution

 #include <bits/stdc++.h>
using namespace std;
#define mx ((int)1e9)
int n,k;
int g[301][301];
void floyd(){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                g[i][j]=g[j][i]=min(g[i][j],g[i][k]+g[k][j]);
            }
        }
    }
}
long long upd(int a,int b,int c){
    if(c>g[a][b])return (long long)0;
    int old=g[a][b],diff=c-g[a][b];
    long long sum=diff;
    g[a][b]=g[b][a]=c;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            int tmp=min(g[i][a]+c+g[b][j],g[i][b]+c+g[a][j]);
            if(tmp<g[i][j]){
                sum+=tmp-g[i][j];
                g[i][j]=g[j][i]=tmp;
            }
        }
    }
    return sum;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>g[i][j];
    cin>>k;
    floyd();
    long long sum=0;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            sum+=g[i][j];
    for(int i=1;i<=k;i++){
        int a,b,c;
        cin>>a>>b>>c;
        sum+=upd(a,b,c);
        cout<<' '<<sum;
    }
return 0;
}