This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <array>
#include <stack>
#include <queue>
#include <random>
#include <numeric>
#include <functional>
#include <chrono>
#include <utility>
#include <iomanip>
#include <assert.h>
using namespace std;
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define rng_seed(x) mt19937 rng(x)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
// #define int long long
rng_init;
const int MXN = 1e5 + 5, INF = 1e9 + 5;
int N, M, K;
vector<pair<int, int>> g[MXN];
vector<array<int, 3>> edges;
vector<int> src[2];
int dist[2][MXN], par[2][MXN];
void dijkstra(int which) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
for (int i = 0; i < N; i++) {
dist[which][i] = INF;
par[which][i] = i;
}
for (const auto &x : src[which]) {
dist[which][x] = 0;
pq.emplace(0, x);
}
while (!pq.empty()) {
auto cur = pq.top();
pq.pop();
int u = cur.second, cur_dist = cur.first;
if (cur_dist != dist[which][u]) continue;
for (const auto &[v, wt] : g[u]) {
int new_dist = cur_dist + wt;
if (new_dist < dist[which][v]) {
dist[which][v] = new_dist;
pq.emplace(new_dist, v);
par[which][v] = par[which][u];
}
}
}
}
int closest_pair(int which) {
int pair_dist = INF;
for (const auto &[u, v, wt] : edges) {
if (par[which][u] == par[which][v]) continue;
pair_dist = min(pair_dist, dist[which][u] + wt + dist[which][v]);
}
return pair_dist;
}
void solve() {
cin >> N >> M >> K;
for (int i = 0; i < M; i++) {
int u, v, w;
cin >> u >> v >> w;
u--, v--;
edges.push_back({u, v, w});
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
vector<int> special(K);
for (auto &x : special) {
cin >> x;
x--;
}
int ans = INF;
for (int iter = 0; iter < 30; iter++) {
src[0].clear(), src[1].clear();
for (const auto &x : special)
src[rng() % 2].push_back(x);
if (sz(src[0]) < 2 || sz(src[1]) < 2) continue;
for (int i = 0; i < 2; i++)
dijkstra(i);
ans = min(ans, closest_pair(0) + closest_pair(1));
}
cout << ans;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int TC = 1;
// cin >> TC;
while (TC--) solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |