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 new roads. For each of the planned road it is known its length, and what cities it will connect. To control the correctness of the construction of new roads, after the opening of another road Berland government wants to check the sum of the shortest distances between all pairs of cities. Help them — for a given matrix of shortest distances on the old roads and plans of all new roads, find out how the sum of the shortest distances between all pairs of cities changes after construction of each road.

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 — di, j, the shortest distance between cities i and j. It is guaranteed thatdi, i = 0, di, j = dj, 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 aibici (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ ci ≤ 1000) — ai and bi — pair of cities, which the road connects, ci — the length of the road. It can be several roads between a pair of cities, but no road connects the city with itself.

Output

Output k space-separated integers qi (1 ≤ i ≤ k). qi 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 <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法修养

CodeForces Roads not only in Berland(并查集)

H - Roads not only in Berland Time Limit:2000MS     Memory Limit:262144KB    ...

2515
来自专栏HansBug's Lab

1648: [Usaco2006 Dec]Cow Picnic 奶牛野餐

1648: [Usaco2006 Dec]Cow Picnic 奶牛野餐 Time Limit: 5 Sec  Memory Limit: 64 MB Subm...

3427
来自专栏ml

HDUOJ ------1398

http://acm.hdu.edu.cn/showproblem.php?pid=1398 Square Coins Time Limit: 2000/100...

2766
来自专栏ml

hust--------The Minimum Length (最短循环节)(kmp)

F - The Minimum Length Time Limit:1000MS     Memory Limit:131072KB     64bit I...

3003
来自专栏ml

hdu---(3779)Railroad(记忆化搜索/dfs)

Railroad Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (...

3505
来自专栏ml

HDUOJ---三角形(组合数学)

http://acm.hdu.edu.cn/showproblem.php?pid=1249 三角形 Time Limit: 2000/1000 MS (Ja...

3337
来自专栏算法修养

POJ-1458 Common Subsequence(线性动规,最长公共子序列问题)

Common Subsequence Time Limit: 1000MS Memory Limit: 10000K Total Submis...

3277
来自专栏算法修养

HOJ 2091 Chess(三维简单DP)

Chess My Tags (Edit) Source : Univ. of Alberta Local Contest 1999.10.16 ...

36510
来自专栏小樱的经验随笔

UVA 11292 Dragon of Loowater(简单贪心)

Problem C: The Dragon of Loowater Once upon a time, in the Kingdom of Loowater, ...

2797
来自专栏小樱的经验随笔

HDU 1039 Easier Done Than Said?

Easier Done Than Said? Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 6...

2816

扫码关注云+社区

领取腾讯云代金券