#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define s second
#define f first
#define pii pair <int,int>
#define left h*2,l,(l + r)/2
#define right h*2+1,(l + r)/2 + 1,r
#define int ll
using namespace std;
const int N = 2e5 + 5,inf = 1e18;
int arr[N],dist[8][N],par[N],n,cur;
bool fix[N];
int dd[37][N],ddd[N];
int DD[37][N],val[37][N];
vector <pii> v[N];
signed main (){
ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
int k,m;
cin>>n>>k>>m;
for (int i = 1; i <= k; i++)
cin >> arr[i];
for (int i =1; i <= m; i++){
int a,b,c;
cin>>a>>b>>c;
v[a].pb({b,c});
v[b].pb({a,c});
}
for (int i = 1; i <= k; i++){
for (int j = 1; j <= n; j++)
dist[i][j] = inf;
priority_queue<pii> pq;
dist[i][arr[i]] = 0;
pq.push({0,arr[i]});
while (pq.size()){
int D = -pq.top().f,x = pq.top().s;
pq.pop();
if (dist[i][x] != D) continue;
for (auto [to,w]: v[x]){
if (dist[i][to] > D + w){
dist[i][to] = D + w;
pq.push({-dist[i][to],to});
}
}
}
}
int ans=inf;
for (int i = 1; i <= n; i++){
int cur=0;
for (int j = 1; j <= k; j++)
cur += dist[j][i];
ans=min(ans,cur);
}
if (k < 4){
cout<<ans<<endl;
exit(0);
}
for (int mask1=0;mask1<(1<<k); mask1++)
for(int i=1;i<=n;i++)
DD[mask1][i] = inf;
for (int mask2=0;mask2<(1<<k); mask2++){
for (int i = 1; i <= n; i++){
for (int j=0;j<k;j++){
if (((mask2>>j) & 1)) val[mask2][i] += (dist[j + 1][i]);
}
}
}
for (int mask1 = 0; mask1 < (1<<k); mask1++){
for (int i = 1; i <= n; i++){
dd[mask1][i] = 0;
for (int j = 0; j < k; j++){
if (((mask1>>j) & 1)) dd[mask1][i] += dist[j + 1][i];
}
}
priority_queue <pii> pq;
for (int i = 1; i <= n; i++)
pq.push({-dd[mask1][i],i});
while (pq.size()){
int D = -pq.top().f,x = pq.top().s;
pq.pop();
if (dd[mask1][x] != D) continue;
for (auto [to,w]: v[x]){
if (dd[mask1][to] > D + w){
dd[mask1][to] = D + w;
pq.push({-dd[mask1][to],to});
}
}
}
for (int mask2 = 0; mask2 < (1<<k); mask2++){
int y = (mask1 & mask2);
if (y > 0) continue;
for (int i = 1; i <= n; i++){
int kk = dd[mask1][i] + val[mask2][i];
DD[(mask1 | mask2)][i] = min(DD[(mask1 | mask2)][i],kk);
}
}
}
for (int mask1=0;mask1<(1<<k); mask1++){
for (int i =1 ; i <= n; i++){
ddd[i] = DD[mask1][i];
}
priority_queue <pii> pq;
for (int i = 1; i <= n; i++)
pq.push({-ddd[i],i});
while (pq.size()){
int D = -pq.top().f,x = pq.top().s;
pq.pop();
if (ddd[x] != D) continue;
for (auto [to,w]: v[x]){
if (ddd[to] > D + w){
ddd[to] = D + w;
pq.push({-ddd[to],to});
}
}
}
for (int i = 1; i <= n; i++){
for (int j =0;j < k; j++){
if (((mask1>>j) & 1)) continue;
ddd[i] += (dist[j + 1][i]);
}
ans=min(ans,ddd[i]);
}
}
cout<<ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
14936 KB |
Output is correct |
2 |
Correct |
1 ms |
14940 KB |
Output is correct |
3 |
Correct |
2 ms |
14940 KB |
Output is correct |
4 |
Correct |
6 ms |
72540 KB |
Output is correct |
5 |
Correct |
6 ms |
72796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
112 ms |
29072 KB |
Output is correct |
2 |
Correct |
107 ms |
29808 KB |
Output is correct |
3 |
Correct |
40 ms |
22096 KB |
Output is correct |
4 |
Correct |
34 ms |
24000 KB |
Output is correct |
5 |
Correct |
92 ms |
27128 KB |
Output is correct |
6 |
Correct |
34 ms |
23816 KB |
Output is correct |
7 |
Correct |
2 ms |
14940 KB |
Output is correct |
8 |
Correct |
2 ms |
14940 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
72620 KB |
Output is correct |
2 |
Correct |
12 ms |
72796 KB |
Output is correct |
3 |
Correct |
10 ms |
72540 KB |
Output is correct |
4 |
Correct |
9 ms |
72540 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
959 ms |
100560 KB |
Output is correct |
2 |
Correct |
883 ms |
99656 KB |
Output is correct |
3 |
Correct |
680 ms |
92960 KB |
Output is correct |
4 |
Correct |
517 ms |
91508 KB |
Output is correct |
5 |
Correct |
152 ms |
83016 KB |
Output is correct |
6 |
Correct |
58 ms |
81532 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2101 ms |
138228 KB |
Output is correct |
2 |
Correct |
2027 ms |
138248 KB |
Output is correct |
3 |
Correct |
1855 ms |
137376 KB |
Output is correct |
4 |
Correct |
1419 ms |
130420 KB |
Output is correct |
5 |
Correct |
1071 ms |
112548 KB |
Output is correct |
6 |
Correct |
250 ms |
89448 KB |
Output is correct |
7 |
Correct |
75 ms |
82548 KB |
Output is correct |