【题解】LuoGu5683：[CSPJX2019]道路拆除

原题传送门
一开始没什么头绪

• 30pts：$O(2^m\ast n)$暴力
• 20pts：一棵树，路径是唯一的，直接把根节点到$s1,s2$的链节选出来，顺便判断一下是不是$<=t1/2$就好了
• 30pts：这时候他让你思考根节点到一个点怎么办，直接选取最短路就好了
• 100pts：前面的其实告诉了我们两个信息：链，最短路
  想一想最终态是怎么样的
  
  既然如此，其实可以直接枚举图中的这个$i$，求最小值就好了
  先预处理出$1,s1,s2$到所有点的最短路

Code：

#include <bits/stdc++.h>
#define maxn 3010
using namespace std;
struct Edge{
	int to, next;
}edge[maxn << 1];
int num, head[maxn], dis[3][maxn], vis[maxn], n, m;
queue <int> q;

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

void addedge(int x, int y){ edge[++num] = (Edge){y, head[x]}, head[x] = num; }

void spfa(int s, int *dis){
	for (int i = 1; i <= n; ++i) dis[i] = 1e9;
	dis[s] = 0;
	memset(vis, 0, sizeof(vis));
	vis[s] = 1;
	q.push(s);
	while (!q.empty()){
		int u = q.front(); q.pop();
		vis[u] = 0;
		for (int i = head[u]; i; i = edge[i].next){
			int v = edge[i].to;
			if (dis[v] > dis[u] + 1){
				dis[v] = dis[u] + 1;
				if (!vis[v]) vis[v] = 1, q.push(v);
			}
		}
	}
}

int main(){
	n = read(), m = read();
	for (int i = 1; i <= m; ++i){
		int x = read(), y = read();
		addedge(x, y), addedge(y, x);
	}
	int s1 = read(), t1 = read(), s2 = read(), t2 = read();
	spfa(1, dis[0]), spfa(s1, dis[1]), spfa(s2, dis[2]);
//	for (int i = 1; i <= n; ++i) printf("dis[%d]=%d\n", i, dis[0][i]);
	int ans = 1e9;
	for (int i = 1; i <= n; ++i)
		if (dis[0][i] + dis[1][i] <= t1 && dis[0][i] + dis[2][i] <= t2) ans = min(ans, dis[0][i] + dis[1][i] + dis[2][i]);
	if (ans < 1e9) printf("%d\n", m - ans); else puts("-1");
	return 0;
}