RC-v4 留下买路财
思路:
地点1, 地点2, A, B A, 地点1(from), 地点2(to) 各自为起点跑一次最短路 注: (from, to)这条路免费 得到关系式 1.A(起点)->B(终点) 2.A(起点)->from(终点), to(起点)->B(终点) 3.A(起点)->to(终点), from(起点)->B(终点)
Code:
#include<bits/stdc++.h> using namespace std;
const int inf = 1e9;int main( ) {ios::sync_with_stdio(false);cin.tie(0); cout.tie(0); int n, m, k; cin >> n >> m >> k;vector<vector<array<int, 2>>> adj(n + 1);map<array<int, 2>, int> mp; for (int i = 1; i <= m; i++) {int from, to, w; cin >> from >> to >> w;adj[from].push_back({w, to});adj[to].push_back({w, from});mp[{from, to}] = w;mp[{to, from}] = w;}auto dijkstra = [&](int s) -> vector<int> {vector<int> dist(n + 1, inf);vector<bool> vis(n + 1, 0);priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>> pq;pq.push({0, s});dist[s] = 0;while(pq.size()) {auto [dw, from] = pq.top();pq.pop();if (vis[from]) {continue;}vis[from] = 1;for (auto [w, to] : adj[from]) {if (dist[to] > dist[from] + w) {dist[to] = dist[from] + w;pq.push({dist[to], to});}}}return dist;} ;while(k--) { int from, to, A, B; cin >> from >> to >> A >> B; auto D1 = dijkstra(A), D2 = dijkstra(from), D3 = dijkstra(to);int ans = inf;if (D1[B] < inf) ans = min(ans, D1[B]);if (D1[from] < inf and D3[B] < inf) ans = min(ans, D1[from] + D3[B] - mp[{from, to}]); if (D1[to] < inf and D2[B] < inf) ans = min(ans, D1[to] + D2[B] - mp[{from, to}]);if (ans >= inf) {cout << "@_@\n";} else {cout << max(0, ans) << '\n';}}return 0;
}
2