This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1<<17;
const ll inf = 1ll<<60;
int n, k, m;
ll dp[32][maxn];
vector<array<int, 2>> g[maxn];
ll z[maxn];
void fix_layer(int msk) {
priority_queue<pair<ll, int>> pq;
for(int i = 1; i <= n; i++) if((z[i] = dp[msk][i]) < inf)
pq.push({-dp[msk][i], i});
while(!pq.empty()) {
auto [di, v] = pq.top();
pq.pop();di *= -1;
//cout << di << " _ " << v << endl;
if(z[v] < di) continue;
for(auto [x, y] : g[v]) {
if(z[x] > di+y) {
z[x] = di+y;
pq.push({-(di+y), x});
}
}
}
for(int i = 1; i <= n; i++) dp[msk][i] = z[i];
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k >> m;
for(int j = 32; j--;)
for(int i = 1; i <= n; i++)
dp[j][i] = inf;
for(int t, i = k; i--;) {
cin >> t;
dp[(1<<i)][t] = 0;
}
for(int f, t, c, i = 0; i < m; i++) {
cin >> f >> t >> c;
g[f].push_back({t, c});
g[t].push_back({f, c});
}
for(int msk = 0; msk < 32; msk++) {
for(int j = msk; j; j = msk&(j-1))
for(int v = 1; v <= n; v++)
dp[msk][v] = min(dp[msk][v], dp[msk^j][v] + dp[j][v]);
fix_layer(msk);
}
ll ans = inf;
for(int i = 1; i <= n; i++)
ans = min(ans, dp[(1<<k)-1][i]);
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... |