专栏首页wym南京网络预选赛 The Preliminary Contest for ICPC Asia Nanjing 2019 H. Holy Grail 多源最短路

南京网络预选赛 The Preliminary Contest for ICPC Asia Nanjing 2019 H. Holy Grail 多源最短路

链接

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 305;
ll g[MAX_N][MAX_N];  // 算法中的 G 矩阵
int n,m; 
void init() {
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				if (i == j) {
					g[i][j] = 0;
				} else {
					g[i][j] = 1e9+10;
				}
		}
	}
}
void insert(int u, int v, ll w) {
	g[u][v] = w;
}
void floyd() {
		for (int k = 0; k < n; ++k) {
			for (int i = 0; i < n; ++i) {
				for (int j = 0; j < n; ++j) {
					if (g[i][k] + g[k][j] < g[i][j]) {
						g[i][j] = g[i][k] + g[k][j];
					}
				}
			}
		}
	}
int main() {
	int _,u,v;
	ll w;
	for(scanf("%d",&_);_;_--){	
		scanf("%d %d",&n,&m);
		init();
		for(int i=1;i<=m;i++){
			scanf("%d %d %lld",&u,&v,&w);
			//insert(v,u,-w);
			insert(u,v,w); 
		}
		floyd();
		for(int l=1;l<=6;l++){
			scanf("%d %d",&u,&v);
			printf("%lld\n",-g[v][u]);
			insert(u,v,-g[v][u]);
			floyd();
		}
	}
	return 0;
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 2038:[2009国家集训队]小Z的袜子(hose)

    用户2965768
  • 2019HDU多校赛第二场 HDU 6601 Keen On Everything But Triangle( 主席树求区间第k大)

    用户2965768
  • Educational Codeforces Round 67 (Rated for Div. 2) A~E 贪心,构造,线段树,树的子树

    Educational Codeforces Round 67 (Rated for Div. 2)

    用户2965768
  • 2038:[2009国家集训队]小Z的袜子(hose)

    用户2965768
  • HDU4609 3-idiots(生成函数)

    但是如果直接算合法的方案的话会出现一点问题。我们在算的时候维护了一个后缀和表示乘起来大于等于这个数的方案。我们要求的方案需要满足i < j < k,但是这样计算...

    attack
  • Topcoder SRM 698 Div1 250 RepeatString(dp)

    attack
  • CodeForces #549 Div.2 C Queen

    ShenduCC
  • LeetCode 593. 有效的正方形(数学)

    Michael阿明
  • View的工作原理

    View的绘制流程是从ViewRoot的PerformTraversals方法开始的。它经过measure,layout,draw三个过程将view绘制出来。m...

    提莫队长
  • HDU5036 Explosion(期望 bitset)

    首先根据期望的线性性,可以转化为求每个点的期望打开次数,又因为每个点最多会被打开一次,只要算每个点被打开的概率就行了

    attack

扫码关注云+社区

领取腾讯云代金券