题目大意：
求图中两两点对最短距离之和
允许你删除一条边，让你最大化删除这个边之后的图中两两点对最短距离之和。
暴力：每次枚举删除哪条边，以每个点为源点做一次最短路，复杂度\(O(NM^2logN)\)。
值得注意的是，\(Dijkstra\)的复杂度\(O(NlogN)\)是关于边而非点的。
这个复杂度对于\(n=100,m=1000\)的数据难以接受。我们考虑对每个点建出其最短路树。容易想到，只有删除到这个点的最短路树上的边时，才需要再做一次\(Dijkstra\)。也就是说每个源点只需要做\(n\)次最短路，复杂度变成\(O(N^2MlogN)\)。
代码实现起来比较麻烦。。本弱调了整整一晚上。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 100 + 5;
const int M = 2000 + 5;
const int INF = 0x3f3f3f3f;
int n, m, l, kase, ban[M];
struct Graph {
int cnt, head[N];
struct Edge {int from, nxt, to, id, w;}e[M];
void clear () {
cnt = -1;
for (int i = 1; i <= n; ++i) {
head[i] = -1;
}
}
void add_edge (int u, int v, int w) {
++cnt; e[cnt] = (Edge) {u, head[u], v, cnt, w}; head[u] = cnt;
}
struct HeapNode {
int u; LL d;
bool operator < (HeapNode rhs) const {
return d > rhs.d;
}
};
priority_queue <HeapNode> pq;
int done[N], _fa[N][N]; LL _dis[N][N];
//dis[i][j] -> i to j
//fa[i][j] -> i as source, j's father
void dijkstra (int s) {
kase = kase + 1;
pq.push ((HeapNode) {s, 0});
LL *dis = _dis[s]; int *fa = _fa[s];
for (int i = 1; i <= n; ++i) {
fa[i] = -1, dis[i] = i == s ? 0 : INF;
}
while (!pq.empty ()) {
HeapNode now = pq.top (); pq.pop ();
if (done[now.u] == kase) continue;
for (int i = head[now.u]; ~i; i = e[i].nxt) {
int v = e[i].to;
if (ban[i]) continue;//禁用的边 -> 不用
if (dis[v] > dis[now.u] + e[i].w) {
fa[v] = now.u;
dis[v] = dis[now.u] + e[i].w;
pq.push ((HeapNode) {v, dis[v]});
}
}
done[now.u] = kase;
}
// cout << "s = " << s << endl;
// for (int i = 1; i <= n; ++i) {
// cout << "dis[" << i << "] = " << dis[i] << endl;
// }
}
}G;
bool have[N][M]; int minw[N][N];
struct Tree {
vector <int> Gr[N];
int sz[N]; LL sum[N], dis[N];
//sz[u] -> 点u的子树大小
//sum[u] -> 点u到其子树里所有点的距离和
void prep (int u) {
sz[u] = 1; sum[u] = dis[u];
for (int i = 0; i < (int)Gr[u].size (); ++i) {
int v = Gr[u][i];
prep (v);
sz[u] += sz[v];
sum[u] += sum[v];
}
}
void build (int s, LL *_dis, int *fa, int cmd) {
for (int i = 1; i <= n; ++i) Gr[i].clear ();
memcpy (dis, _dis, sizeof (dis));
for (int i = 1; i <= n; ++i) {
if (fa[i] != -1) {
Gr[fa[i]].push_back (i);
if (cmd == 1) {
have[fa[i]][i] = true;
have[i][fa[i]] = true;
}
}
}
prep (s);
// for (int i = 1; i <= n; ++i) {
// cout << "dis[" << i << "] = " << dis[i] << endl;
// cout << "sum[" << i << "] = " << sum[i] << endl;
// }
}
LL get_ans (int s, LL *_dis, int *fa, int cmd) {
build (s, _dis, fa, cmd);
return sum[s] + (n - sz[s]) * l;
}
}tr[N];//tr[i] -> 点i的最短路树
signed main () {
// freopen ("data.in", "r", stdin);
// freopen ("data.out", "w", stdout);
while (cin >> n >> m >> l) {
G.clear ();
memset (have, 0, sizeof (have));
memset (minw, 0x3f, sizeof (minw));
for (int i = 1; i <= m; ++i) {
static int u, v, w;
cin >> u >> v >> w;
G.add_edge (u, v, w);
G.add_edge (v, u, w);
minw[u][v] = min (minw[u][v], w);
minw[v][u] = min (minw[v][u], w);
}
LL ans1 = 0, ans2 = 0;
for (int s = 1; s <= n; ++s) {
G.dijkstra (s);
ans1 += tr[s].get_ans (s, G._dis[s], G._fa[s], 1);
//存一下最初的have
}
cout << ans1 << " ";
for (int i = 0; i <= G.cnt; i += 2) {
//每次枚举禁用一条边。
LL res_now = 0;
ban[i] = ban[i + 1] = true;//双向都要禁
for (int s = 1; s <= n; ++s) { //枚举删除之后每一棵最短路树的状况
int u = G.e[i].from, v = G.e[i].to, w = G.e[i].w;
if (have[u][v] && w == minw[u][v]) G.dijkstra (s);
res_now += tr[s].get_ans (s, G._dis[s], G._fa[s], 0);
}
ban[i] = ban[i + 1] = false;
ans2 = max (ans2, res_now);
}
cout << ans2 << endl;
}
}