CodeForces 25C(Floyed 最短路)

F - Roads in Berland

Time Limit:2000MS     Memory Limit:262144KB     64bit IO Format:%I64d

& %I64u

Submit ​​Status​​​ ​​Practice​​​ ​​CodeForces 25C​​

Description

There are n cities numbered from 1 to n in Berland. Some of them are connected by two-way roads. Each road has its own length — an integer number from 1 to 1000. It is known that from each city it is possible to get to any other city by existing roads. Also for each pair of cities it is known the shortest distance between them. Berland Government plans to build k

Input

The first line contains integer n (2 ≤ n ≤ 300) — amount of cities in Berland. Then there follow n lines with n integer numbers each — the matrix of shortest distances. j-th integer in the i-th row — d_i, j, the shortest distance between cities i and j. It is guaranteed thatd_i, i = 0, d_i, j = d_j, i, and a given matrix is a matrix of shortest distances for some set of two-way roads with integer lengths from 1 to 1000, such that from each city it is possible to get to any other city using these roads.

Next line contains integer k (1 ≤ k ≤ 300) — amount of planned roads. Following k lines contain the description of the planned roads. Each road is described by three space-separated integers a_i, b_i, c_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i, 1 ≤ c_i ≤ 1000) — a_i and b_i — pair of cities, which the road connects, c_i

Output

Output k space-separated integers q_i (1 ≤ i ≤ k). q_i should be equal to the sum of shortest distances between all pairs of cities after the construction of roads with indexes from 1 to i. Roads are numbered from 1 in the input order. Each pair of cities should be taken into account in the sum exactly once, i. e. we count unordered pairs.

Sample Input

Input

2
0 5
5 0
1
1 2 3

Output

3

Input

3
0 4 5
4 0 9
5 9 0
2
2 3 8
1 2 1

Output

17 12

这道题目对每次增加的路跑一下Floyed就好了，输出格式好像没有限制

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
int a[305][305];
int k;
int n;
int x,y,z;
int main()
{
   scanf("%d",&n);
   int sum=0;
   for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
      {scanf("%d",&a[i][j]);sum+=a[i][j];}
   sum/=2;
   scanf("%d",&k);
   long long int num;
   for(int i=1;i<=k;i++)
   {
       scanf("%d%d%d",&x,&y,&z);
      num=0;
      if(a[x][y]>z)
      {
        // sum-=(a[x][y]-z);
        a[x][y]=z;
        a[y][x]=z;
      }
      for(int i=1;i<=n;i++)
      {
         for(int j=1;j<=n;j++)
         {

             if(a[i][j]>(a[i][x]+a[y][j]+a[x][y]))
             {
               
                 //num=(a[i][j]-a[i][x]-a[y][j]-a[x][y]);
                     //sum-=(a[i][j]-a[i][x]-a[y][j]-a[x][y]);
                a[i][j]=(a[i][x]+a[y][j]+a[x][y]);
                //a[j][i]=(a[i][x]+a[y][j]+a[x][y]);
                
             }
             if(a[i][j]>(a[i][y]+a[x][j]+a[x][y]))
             {
                //num=(a[i][j]-a[i][x]-a[y][j]-a[x][y]);
                     //sum-=(a[i][j]-a[i][y]-a[x][j]-a[x][y]);
                a[i][j]=(a[i][y]+a[x][j]+a[x][y]);
                //a[j][i]=(a[i][y]+a[x][j]+a[x][y]);
                
             }
             num+=a[i][j];

         }
      }
      printf("%lld ",num/2);
      
   }
   printf("\n");
   return 0;
}