H.Holy Grail(2019 icpc 南京网络赛)

题目

Input

Output

思路： 添加6条边（最小），使图中没有负回路，网上大部分题解用SPFA，但官方是跑了6遍Floyd，然后就有答案了，这种方法能够显著减少码量。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>using namespace std;typedef long long ll;const int inf = 0x3f3f3f3f;ll dp[303][303];
int n, m;
int a, b;
ll c;int main()
{int t;scanf("%d", &t);while (t--){scanf("%d %d", &n, &m);// 初始化for (int i = 0; i <= 300; ++i)for (int j = 0; j <= 300; ++j)dp[i][j] = inf;for (int i = 1; i <= m; ++i){scanf("%d%d%lld", &a, &b, &c);dp[a][b] = c;}for (int d = 1; d <= 6; ++d){scanf("%d%d", &a, &b);for (int k = 0; k < n; ++k)for (int i = 0; i < n; ++i)for (int j = 0; j < n; ++j)dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);printf("%lld\n", -dp[b][a]);dp[a][b] = -dp[b][a];}}return 0;
}