题意
给定一个无向图，含有 \(n\) 个点和 \(m\) 条边。
题解
点击查看代码
#include <bits/stdc++.h>using namespace std;using i64 = long long;constexpr i64 inf = 1e18;void solve() {int n, m, h;cin >> n >> m >> h;vector<vector<pair<int, int>>> adj(2 * n);for (int i = 0; i < h; i++) {int a;cin >> a;a--;adj[a].emplace_back(a + n, 0);}for (int i = 0; i < m; i++) {int u, v, w;cin >> u >> v >> w;u--; v--;adj[u].emplace_back(v, w);adj[v].emplace_back(u, w);adj[u + n].emplace_back(v + n, w / 2);adj[v + n].emplace_back(u + n, w / 2);}auto dijkstra = [&](int s) {priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<pair<i64, int>>> Q;vector<i64> dist(2 * n, inf);vector<bool> vis(2 * n, false);dist[s] = 0LL;Q.emplace(0LL, s);while (!Q.empty()) {int u = Q.top().second;Q.pop();if (vis[u]) {continue;}vis[u] = true;for (auto [v, w] : adj[u]) {if (dist[v] > dist[u] + w) {dist[v] = dist[u] + w;Q.emplace(dist[v], v);}}}vector<i64> ans(n);for (int i = 0; i < n; i++) {ans[i] = min(dist[i], dist[i + n]);}return ans;};vector<i64> D1 = dijkstra(0), D2 = dijkstra(n - 1);i64 ans = inf;for (int i = 0; i < n; i++) {ans = min(ans, max(D1[i], D2[i]));}if (ans == inf) {ans = -1;}cout << ans << "\n";
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin >> T;while (T--) {solve();}return 0;
}
