meaning of the title

In a graph, some edges on the shortest path are removed to make the shortest path unconnected, to judge whether the scheme is unique and to find the sum of edge weights of the least removed edges.

thinking

First, take out the points on the shortest path.

It is obvious that removing edge disjunction is to find the minimum cut, and then judge whether the minimum cut is unique.

In residue networks, if the edge (u,v)(u,v)(u,v), u ∈ Su\in Su ∈ S, v ∈ Tv\in Tv ∈ T, then the edge must be cut.
Judge the sum of the capacity of the edge to be cut and the minimum cut.

Code

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>

const long long N = 4501, M = 8001, inf = 1 << 29;
int n, m, tot, totn, s, t, mid;
long long ans;
long long a[N], edge[M], edgen[M], dis1[N], dis2[N];
int arrs[N], arrt[N];
int ver[M], head[N], next[M];
int vern[M], headn[N], nextn[M];
int v[N], dep[N];

void add(int u, int v, long long w) {
	ver[++tot] = v;
	edge[tot] = w;
	next[tot] = head[u];
	head[u] = tot;
	ver[++tot] = u;
	edge[tot] = w;
	next[tot] = head[v];
	head[v] = tot;
}

void addn(int u, int v, long long w) {
	vern[++totn] = v;
	edgen[totn] = w;
	nextn[totn] = headn[u];
	headn[u] = totn;
	vern[++totn] = u;
	edgen[totn] = 0;
	nextn[totn] = headn[v];
	headn[v] = totn;
}

void spfa1() {
	memset(dis1, 127 / 3, sizeof(dis1));
	memset(v, 0, sizeof(v));
	std::queue<int> q;
	q.push(1);
	dis1[1] = 0;
	v[1] = 1;
	while (q.size()) {
		int x = q.front();
		q.pop();
		v[x] = 0;
		for (int i = head[x]; i; i = next[i])
			if (dis1[ver[i]] > dis1[x] + edge[i]) {
				dis1[ver[i]] = dis1[x] + edge[i];
				if (!v[ver[i]]) {
					q.push(ver[i]);
					v[ver[i]] = 1;
				}
			}
	}
}

void spfa2() {
	memset(dis2, 127 / 3, sizeof(dis2));
	memset(v, 0, sizeof(v));
	std::queue<int> q;
	q.push(n);
	dis2[n] = 0;
	v[n] = 1;
	while (q.size()) {
		int x = q.front();
		q.pop();
		v[x] = 0;
		for (int i = head[x]; i; i = next[i])
			if (dis2[ver[i]] > dis2[x] + edge[i]) {
				dis2[ver[i]] = dis2[x] + edge[i];
				if (!v[ver[i]]) {
					q.push(ver[i]);
					v[ver[i]] = 1;
				}
			}
	}
}

int bfs() {
	memset(dep, 0, sizeof(dep));
	std::queue<int> q;
	dep[s] = 1;
	q.push(s);
	while (q.size()) {
		int x = q.front();
		q.pop();
		for (int i = headn[x]; i; i = nextn[i])
			if (edgen[i] && !dep[vern[i]]) {
				dep[vern[i]] = dep[x] + 1;
				if (vern[i] == t) return 1;
				q.push(vern[i]);
			}
	}
	return 0;
}

long long dfs(int p, long long flow) {
	if (p == t) return flow;
	long long rest = flow;
	for (int i = headn[p]; i && rest; i = nextn[i]) {
		if (dep[vern[i]] == dep[p] + 1 && edgen[i]) {
			long long k = dfs(vern[i], std::min(rest, edgen[i]));
			if (!k) dep[vern[i]] = 0;
			edgen[i] -= k;
			edgen[i ^ 1] += k;
			rest -= k;
		}
	}
	return flow - rest;
}

void dinic() {
	long long flow = 0;
	while (bfs())
		while (flow = dfs(s, inf)) ans += flow;
}

void dfss(int p) {
	arrs[p] = 1;
	for (int i = headn[p]; i; i = nextn[i])
		if (!arrs[vern[i]] && edgen[i]) dfss(vern[i]);
}

void dfst(int p) {
	arrt[p] = 1;
	for (int i = headn[p]; i; i = nextn[i])
		if (!arrt[vern[i]] && edgen[i ^ 1]) dfst(vern[i]);
}

int main() {
	int T;
	scanf("%d", &T);
	for (; T; T--) {
		scanf("%d %d", &n, &m);
		tot = 1;
		totn = 1;
		s = 1;
		t = n;
		ans = 0;
		memset(head, 0, sizeof(head));
		memset(headn, 0, sizeof(headn));
		memset(arrs, 0, sizeof(arrs));
		memset(arrt, 0, sizeof(arrt));
		for (long long i = 1; i < n; i++)
			scanf("%d", &a[i]);
		a[n] = inf;
		for (long long i = 1, x, y, z; i <= m; i++) {
			scanf("%d %d %lld", &x, &y, &z);
			add(x, y, z);
	 	}
	 	spfa1();
	 	spfa2();
	 	mid = n;
		for (long long i = 2; i <= tot; i++) {
			long long x = ver[i ^ 1], y = ver[i];
			if (dis1[x] + dis2[x] != dis1[n] || dis1[y] + dis2[y] != dis1[n]) continue;
			if (dis1[x] + edge[i] == dis1[y]) {
				addn(x, ++mid, a[x]);
				addn(mid, y, a[y]);
			}
		}
		dinic();
		dfss(s);
		dfst(t);
		long long res = 0;
		for (int i = 1; i <= mid; i++) if (arrs[i])
			for (int j = headn[i]; j; j = nextn[j])
				if (arrs[i] && arrt[vern[j]])
					res += edgen[j ^ 1];
		res == ans ? printf("Yes ") : printf("No ");
		printf("%lld\n", ans);
	}
}