[原题传送门](http://https://www.luogu.com.cn/problem/P5683 "原题传送门") ### 题意分析 - 30pts：O(2^m*n))暴力 - 20pts：一棵树，路径是唯一的，直接把根节点到2s1,s2的链节选出来，顺便判断一下是不是<=t1/2就好了 - 30pts：这时候他让你思考根节点到一个点怎么办，直接选取最短路就好了 - 100pts：前面的其实告诉了我们两个信息：链，最短路 想一想最终态是怎么样的  既然如此，其实可以直接枚举图中的这个i ii，求最小值就好了 先预处理出1,s1,s2到所有点的最短路 ### 代码 ```cpp #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; } ```