医药网站建设需要注意点,百度seo优化教程,直接做网站的软件,软文营销常用的方式链接
这是一个比较经典的题目。容易想到求出两段路径重合的部分#xff0c;然后贪心的放权值。那么跑三次最短路#xff0c;枚举重合部分的端点即可。
正解没什么好说的。这题有趣的地方在于#xff0c;如果数据比较弱#xff0c;可能会把一些错误做法放过去。
一种错误…链接
这是一个比较经典的题目。容易想到求出两段路径重合的部分然后贪心的放权值。那么跑三次最短路枚举重合部分的端点即可。
正解没什么好说的。这题有趣的地方在于如果数据比较弱可能会把一些错误做法放过去。
一种错误做法是只求 aaa 点和 ccc 点的单源最短路然后在枚举端点的时候认为端点一定在 a,ba,ba,b 或者 b,cb,cb,c 之间的最短路径上。这个结论是错误的可以构造出这样的反例
7 8 1 4 6
1 2 3 4 100 100 100 100
1 2
2 3
3 4
3 5
5 6
3 7
1 7
6 7这里的答案显然是 131313而错误做法可能会得到 111111111。
这种构造的依据是最短路并不是唯一的。然而即便最短路是唯一的上面的做法依然不正确。不妨设 a,ba,ba,b 与 b,cb,cb,c 两条最短路径共用了从点 mmm 到点 bbb 的路径mmm 到 a,b,ca,b,ca,b,c 三个点的距离分别为 100,10,100100,10,100100,10,100而在这两条路径外面有一个点 nnn它到三个点的距离分别为 90,30,9090,30,9090,30,90那么这个 nnn 点在上面的做法中是不会被遍历到的但只需设计好权值就可以使最优解经过这个点。
下面是正解的代码最短路用 BFS 实现更好。
#include bits/stdc.h
using namespace std;
#define pb push_back
using ll long long;
const int maxn 2e5 5;
const ll inf 1e18;
vectorint g[maxn];
void solve() {int n, m, A, B, C;cin n m A B C;vectorll w(m);for (auto i : w) cin i;for (int i 1, u, v; i m; i) {cin u v;g[u].pb(v);g[v].pb(u);}sort(w.begin(), w.end());vectorint disA(n 1, 0x3f3f3f3f);vectorint disB(n 1, 0x3f3f3f3f);vectorint disC(n 1, 0x3f3f3f3f);vectorint p(n 1);functionvoid(int, vectorint) dijkstra [](int s, vectorint d) {vectorint vis(n 1, 0);struct node {int id, dis;bool operator (const node rhs) const {return (dis rhs.dis ? id rhs.id : dis rhs.dis);}};priority_queuenode q;d[s] 0;q.push({ s, 0 });while (!q.empty()) {auto [cur, cost] q.top();q.pop();if (vis[cur]) continue;vis[cur] 1;d[cur] cost;for (auto to : g[cur]) {if (vis[to]) continue;if (d[to] d[cur] 1) {d[to] d[cur] 1;q.push({ to, d[to] });p[to] cur;}}}};vectorll pre(m 1, 0);for (int i 1; i m; i) {pre[i] pre[i - 1] w[i - 1];}dijkstra(A, disA);dijkstra(B, disB);dijkstra(C, disC);ll ans inf;for (int i 1; i n; i) {int da disA[i], db disB[i], dc disC[i];if (da db dc m) continue;ans min(ans, pre[db] pre[da db dc]);}cout ans endl;for (int i 1; i n; i) {g[i].clear();}
}
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T 1;cin T;while (T--) {solve();}return 0;
}
