专栏首页算法修养CodeForces 25C(Floyed 最短路)

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 条评论
登录 后参与评论

相关文章

  • ZOJ 3210 A Stack or A Queue?

    A Stack or A Queue? ---- Time Limit: 1 Second      Memory Limit: 32768 KB ---- D...

    ShenduCC
  • ZOJ 3705 Applications

    Recently, the ACM/ICPC team of Marjar University decided to choose some new memb...

    ShenduCC
  • PAT 甲级 1003Emergency(Dijkstra最短路)

    1003. Emergency (25) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序...

    ShenduCC
  • NeurIPS2019研讨会(发展中国家的机器学习)论文集:ML4D的挑战和风险(CS Society)

    这是第三届ML4D研讨会的会议记录,该研讨会于2019年12月13日在加拿大温哥华举行,是神经信息处理系统会议的一部分。

    shellmik
  • STL 训练 POJ - 1862 Stripies

    Our chemical biologists have invented a new very useful form of life called stri...

    风骨散人Chiam
  • 目标检测

    A Unified Multi-scale Deep Convolutional Neural Network for Fast Object Detectio...

    用户1148525
  • 工人的请愿书(树形DP)- UVA 12186

    A couple of years ago, a new world wide crisis started, leaving many people with...

    ACM算法日常
  • Java实现尺取法

    同学推荐的一题,看了别人及讲解,学到了一点新的东西------尺取法 例题如下: Description

    萌萌哒的瓤瓤
  • Python文档研读系列:zip函数

    zip([iterable, ...]) This function returns a list of tuples, where the i-th tupl...

    Python中文社区
  • R Programming-week1 Reading Data

    There are a few principal functions readingdata into R.

    统计学家

扫码关注云+社区

领取腾讯云代金券