#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 2e17, MAXN = 1e5 + 1, mod = 1e9 + 7;
vector<pair<int, ll>> g[MAXN];
vector<int> imp;
vector<ll> dejkstra(int v, int n) {
vector<ll> dist(n, INF);
dist[v] = 0;
set<pair<ll, int>> q;
q.insert({ 0, v });
while (!q.empty()) {
int cur = (*q.begin()).second;
q.erase(q.begin());
for (auto& [to, c] : g[v]) {
if (dist[to] > dist[v] + c) {
dist[to] = dist[v] + c;
q.insert({ dist[to], to });
}
}
}
return dist;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k, m;
cin >> n >> k >> m;
imp.resize(k);
for (int i = 0; i < k; ++i) {
cin >> imp[i];
imp[i]--;
}
for (int i = 0; i < m; ++i) {
int a, b, c;
cin >> a >> b >> c;
--a, --b;
g[a].push_back({ b, c });
g[b].push_back({ a, c });
}
if (k == 2 || k == 3) {
vector<vector<ll>> dist(k);
for (int i = 0; i < k; ++i) {
dist[i] = dejkstra(imp[i], n);
}
ll ans = INF;
for (int i = 0; i < n; ++i) {
ll cur = 0;
for (auto& x : dist) {
cur += x[i];
}
ans = min(ans, cur);
}
cout << ans << '\n';
}
}
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |