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 <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
const long long inf = 1e18;
int n, k, m; cin >> n >> k >> m;
vector<int> city(k);
for (int &u : city) {
cin >> u; --u;
}
vector<vector<array<int, 2>>> g(n);
while (m--) {
int u, v, c; cin >> u >> v >> c; --u, --v;
g[u].push_back({v, c});
g[v].push_back({u, c});
}
vector d(n, vector<long long>(1 << k, inf));
using T = tuple<long long, int, int>;
priority_queue<T, vector<T>, greater<T>> pq;
for (int i = 0; i < k; ++i) {
d[city[i]][1 << i] = 0;
pq.push({0, city[i], 1 << i});
}
while (pq.size()) {
auto [c, u, m] = pq.top(); pq.pop();
if (c != d[u][m]) {
continue;
}
for (auto [v, w] : g[u]) {
if (d[v][m] > c + w) {
pq.push({d[v][m] = c + w, v, m});
}
}
int mm = (1 << k) - 1 - m;
for (int sm = mm; sm; sm = (sm - 1) & mm) {
if (d[u][sm + m] > c + d[u][sm]) {
pq.push({d[u][sm + m] = c + d[u][sm], u, sm + m});
}
}
}
long long res = inf;
for (int i = 0; i < n; ++i) {
res = min(res, d[i].back());
}
cout << res;
return 0;
}
# | 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... |