百度之星2023——公园

这道题目用bfs做反而麻烦了。

首先抓题目关键字，要求“最少”，那大概率就是最短路径问题。虽然这题是一个无权图，用bfs也能求最短路径，但是我们知道使用dijkstra是能够利用dist数组持久化最短路径的，相比每次都要bfs，使用dijkstra能够起到空间换时间的效果。

回到这题本身，提供2个起始点+1个终点（假设分别为A,B,C），那么就是要再找一个结点D，使得A, B先单独到D，然后再一起到C（CD重合是一种特例），这个过程总消耗最少。那么就分别以A, B, C为起点进行三次dijkstra，得到三个最短路径数组。然后穷举图中每一个点作为D，如果D能够与A, B, C都连通，就计算一次总消耗。穷举完毕，得到最小消耗。

这题想要有思路那么一定得突破一种思维局限：穷举法并非暴力法！

#include<bits/stdc++.h> 
using namespace std;int TE, FE, S, T, F, N, M;
vector<vector<int>> graph; //邻接表struct Pair {int v, w;Pair(int a, int b): v(a), w(b){}bool operator<(const Pair& p) const {return w > p.w;} 
};void dijkstra(vector<int>& dist, int& start) {priority_queue<Pair> pq;Pair p(start, 0);pq.push(p);while (!pq.empty()) {p = pq.top();pq.pop();if (p.w > dist[p.v]) {continue;}for (auto& v: graph[p.v]) {if (dist[v] > p.w + 1) {dist[v] = p.w + 1;Pair cur(v, dist[v]);pq.push(cur);}}}	
}int main( )
{cin >> TE >> FE >> S >> T >> F >> N >> M;graph.resize(N + 1, vector<int>());for (int i = 0; i < M; ++i) {int x, y;cin >> x >> y;graph[x].emplace_back(y);graph[y].emplace_back(x);}vector<int> distN(N + 1, INT_MAX);vector<int> distT(N + 1, INT_MAX);vector<int> distF(N + 1, INT_MAX);distN[N] = 0;distT[T] = 0;distF[F] = 0;dijkstra(distN, N);dijkstra(distT, T);dijkstra(distF, F);bool isAccess = false; //是否可达long long minCost = LONG_MAX;for (int i = 1; i <= N; ++i) {if (distN[i] == INT_MAX || distT[i] == INT_MAX || distF[i] == INT_MAX) {// 不能连通continue;}isAccess = true;minCost = min(minCost, (long long)TE * distT[i] + (long long)FE * distF[i] + (long long)(TE + FE - S) * distN[i]);}if (isAccess) {cout << minCost << endl;	} else {cout << -1 << endl;}return 0;
}