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>
#define va first
#define vb second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int MN = 1e5+5;
long long N,K,M,A,B,d,sz,Im[5],cur,tmp,cost,ans,D[32][MN];
vector<pii> G[MN];
priority_queue<pii> Q;
int main()
{
ios_base::sync_with_stdio(0),cin.tie(0);
cin >> N >> K >> M;
for(int i=0; i<K; i++) cin >> Im[i];
for(int i=0; i<M; i++){
cin >> A >> B >> d;
G[A].push_back(pii(B,d));
G[B].push_back(pii(A,d));
}
sz = 1<<K;
for(int i=0; i<sz; i++)
for(int j=1; j<=N; j++) D[i][j] = 1e18;
for(int j=0; j<K; j++) D[(1<<j)][Im[j]] = 0;
for(int i=1; i<sz; i++){
for(int j=1; j<=N; j++){
tmp = 1e18;
for(int p=1; p<sz; p++){
if((p&i)!=p) continue;
tmp = min(tmp,D[i-p][j] + D[p][j]);
}
D[i][j] = min(D[i][j],tmp);
Q.emplace(-D[i][j],j);
}
while(!Q.empty()){
cur = Q.top().vb;
cost = -Q.top().va;
Q.pop();
if(cost>D[i][cur]) continue;
for(pii x : G[cur]){
if(D[i][x.va] > cost + x.vb){
D[i][x.va] = cost + x.vb;
Q.emplace(-D[i][x.va],x.va);
}
}
}
}
ans = 1e18;
for(int j=1; j<=N; j++) ans = min(ans,D[sz-1][j]);
cout << ans;
}
# | 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... |