// oooo
/*
har chi delet mikhad bebar ~
gitar o ba khodet nabar! ~
;Amoo_Hasan;
*/
#include<bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")
using namespace std;
typedef long long ll;
typedef long double ld;
#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl
constexpr ll inf = 1e18, N = 1e6 + 10, mod = 1e9 + 7, pr = 1000696969;
int n, m, k;
ll d[N][6], dp[N][6], sp[N];
vector<pair<int, ll> > G[N];
vector<int> vc;
inline void dijk(int x, int pos) {
for(int j = 0; j < n; j++) d[j][pos] = inf;
set<pair<ll, int> > st;
d[x][pos] = 0, st.insert({0, x});
while(!st.empty()) {
int p = st.begin() -> second; st.erase(st.begin());
for(auto i : G[p]) {
if(d[i.first][pos] > d[p][pos] + i.second) {
st.erase({d[i.first][pos], i.first});
d[i.first][pos] = d[p][pos] + i.second;
st.insert({d[i.first][pos], i.first});
}
}
}
}
inline void dojob(int ind1, int ind2, int ind3) {
for(int i = 0; i < n; i++) dp[i][ind1] = inf;
set<pair<int, ll> > st;
vector<int> res;
res.push_back(ind1), res.push_back(ind2), res.push_back(ind3);
/* for(auto x : res) {
for(int i = 0; i < n; i++) {
sp[i] = d[i][x];
st.insert({sp[i], i});
}
while(!st.empty()) {
int p = st.begin() -> second; st.erase(st.begin());
for(auto i : G[p]) {
if(sp[i.first] > sp[p] + i.second) {
st.erase({sp[i.first], i.first});
sp[i.first] = sp[p] + i.second;
st.insert({sp[i.first], i.first});
}
}
}
for(int i = 0; i < n; i++) {
ll sum = d[i][ind1] + d[i][ind2] + d[i][ind3] - d[i][x];
dp[i][ind1] = min(dp[i][ind1], sum + sp[i]);
}
}*/
for(auto x : res) {
for(auto x2 : res) {
if(x == x2 || x > x2) continue;
for(int i = 0; i < n; i++) {
sp[i] = d[i][x] + d[i][x2];
st.insert({sp[i], i});
}
while(!st.empty()) {
int p = st.begin() -> second; st.erase(st.begin());
for(auto i : G[p]) {
if(sp[i.first] > sp[p] + i.second) {
st.erase({sp[i.first], i.first});
sp[i.first] = sp[p] + i.second;
st.insert({sp[i.first], i.first});
}
}
}
for(int i = 0; i < n; i++) {
ll sum = d[i][ind1] + d[i][ind2] + d[i][ind3] - d[i][x] - d[i][x2];
dp[i][ind1] = min(dp[i][ind1], sum + sp[i]);
}
}
}
}
int main() {
ios :: sync_with_stdio(0), cin.tie(0);
cin >>n >>k >>m;
for(int i = 0; i < k; i++) {
int v; cin >>v; v--, vc.push_back(v);
}
for(int i = 0; i < m; i++) {
int u, v, w; cin >>u >>v >>w;
u--, v--;
G[u].push_back({v, w}), G[v].push_back({u, w});
}
if(k == 2) {
int u = vc[0], v = vc[1];
dijk(u, 0);
cout<<d[v][0] <<endl;
return 0;
}
if(k == 3) {
int pos = -1;
for(auto x : vc) { pos++;
dijk(x, pos);
}
ll ans = inf;
for(int i = 0; i < n; i++) {
ans = min(ans, d[i][0] + d[i][1] + d[i][2]);
}
cout<<ans;
return 0;
}
ll ans = inf;
if(k == 4) {
for(int i = 0; i < 4; i++) {
dijk(vc[i], i);
}
for(int i = 1; i < 4; i++) {
int ind1 = -1, ind2 = -1;
for(int j = 1; j < 4; j++) {
if(j == i) continue;
if(ind1 == -1) ind1 = j;
else ind2 = j;
}
for(int j = 0; j < n; j++) {
dp[j][ind1] = d[j][ind1] + d[j][ind2];
dp[j][ind2] = 0;
}
set<pair<ll, int> > st;
for(int j = 0; j < n; j++) {
st.insert({d[j][0] + d[j][i], j});
dp[j][ind2] = d[j][0] + d[j][i];
}
while(!st.empty()) {
int p = st.begin() -> second; st.erase(st.begin());
for(auto i : G[p]) {
if(dp[i.first][ind2] > dp[p][ind2] + i.second) {
st.erase({dp[i.first][ind2], i.first});
dp[i.first][ind2] = dp[p][ind2] + i.second;
st.insert({dp[i.first][ind2], i.first});
}
}
}
for(int j = 0; j < n; j++) {
ans = min(ans, dp[j][ind2] + dp[j][ind1]);
}
}
cout<<ans;
return 0;
}
for(int i = 0; i < 5; i++) {
dijk(vc[i], i);
}
for(int i = 1; i < 5; i++) {
int ind1 = -1, ind2 = -1, ind3 = -1;
for(int j = 1; j < 5; j++) {
if(j == i) continue;
if(ind1 == -1) ind1 = j;
else if(ind2 == -1) ind2 = j;
else ind3 = j;
}
dojob(ind1, ind2, ind3);
for(int j = 0; j < n; j++) {
dp[j][ind2] = 0;
}
set<pair<ll, int> > st;
for(int j = 0; j < n; j++) {
st.insert({d[j][0] + d[j][i], j});
dp[j][ind2] = d[j][0] + d[j][i];
}
while(!st.empty()) {
int p = st.begin() -> second; st.erase(st.begin());
for(auto i : G[p]) {
if(dp[i.first][ind2] > dp[p][ind2] + i.second) {
st.erase({dp[i.first][ind2], i.first});
dp[i.first][ind2] = dp[p][ind2] + i.second;
st.insert({dp[i.first][ind2], i.first});
}
}
}
for(int j = 0; j < n; j++) {
ans = min(ans, dp[j][ind2] + dp[j][ind1]);
}
}
cout<<ans;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 2 |
Correct |
12 ms |
23780 KB |
Output is correct |
| 3 |
Correct |
12 ms |
23764 KB |
Output is correct |
| 4 |
Correct |
13 ms |
23812 KB |
Output is correct |
| 5 |
Correct |
15 ms |
23952 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
361 ms |
45316 KB |
Output is correct |
| 2 |
Correct |
402 ms |
46012 KB |
Output is correct |
| 3 |
Correct |
129 ms |
35872 KB |
Output is correct |
| 4 |
Correct |
79 ms |
36128 KB |
Output is correct |
| 5 |
Correct |
205 ms |
45308 KB |
Output is correct |
| 6 |
Correct |
76 ms |
36064 KB |
Output is correct |
| 7 |
Correct |
15 ms |
24020 KB |
Output is correct |
| 8 |
Correct |
14 ms |
24020 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
16 ms |
24020 KB |
Output is correct |
| 2 |
Correct |
16 ms |
24020 KB |
Output is correct |
| 3 |
Correct |
14 ms |
24020 KB |
Output is correct |
| 4 |
Correct |
16 ms |
23952 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
962 ms |
53668 KB |
Output is correct |
| 2 |
Correct |
938 ms |
52904 KB |
Output is correct |
| 3 |
Correct |
499 ms |
46824 KB |
Output is correct |
| 4 |
Correct |
575 ms |
45612 KB |
Output is correct |
| 5 |
Correct |
163 ms |
37612 KB |
Output is correct |
| 6 |
Correct |
76 ms |
38316 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3066 ms |
54484 KB |
Output is correct |
| 2 |
Correct |
3027 ms |
54472 KB |
Output is correct |
| 3 |
Correct |
3003 ms |
53692 KB |
Output is correct |
| 4 |
Correct |
3207 ms |
47564 KB |
Output is correct |
| 5 |
Correct |
1674 ms |
45880 KB |
Output is correct |
| 6 |
Correct |
304 ms |
37680 KB |
Output is correct |
| 7 |
Correct |
88 ms |
38424 KB |
Output is correct |
