#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5+10, M = 8e5+10;
const long long oo = 1e18+10;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
vector<vector<pair<int, long long>>> edges(n+1);
for(int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
edges[u].push_back({v, w});
edges[v].push_back({u, w});
}
priority_queue<vector<long long>> q;
vector<int> special(k+1);
vector<bool> is_special(n+1);
for(int i = 1; i <= k; ++i) {
cin >> special[i];
is_special[special[i]] = 1;
q.push({0, special[i], special[i]});
}
vector<vector<long long>> v;
map<pair<int,int>, bool> seen;
int op = M;
while(!q.empty() && --op) {
auto t = q.top(); q.pop();
if(t[1] == t[2] && t[0]) continue;
if(t[1] != t[2] && is_special[t[1]] && seen.find({t[1], t[2]}) == seen.end()) {
v.push_back({-t[0], min(t[1], t[2]), max(t[1], t[2])});
seen[{t[1], t[2]}]; seen[{t[2], t[1]}];
}
for(auto to : edges[t[1]]) {
q.push({t[0] - to.second, to.first, t[2]});
}
}
sort(v.begin(), v.end());
const int BLOCK_SIZE = 500;
const int BLOCK_COUNT = N / BLOCK_SIZE;
map<int, int> cnt_one[BLOCK_COUNT];
map<pair<int,int>, int> cnt_two[BLOCK_COUNT];
for(int i = 0, block = -1; i < (int)v.size(); ++i) {
if(i % BLOCK_SIZE == 0) ++block;
cnt_one[block][v[i][1]]++;
cnt_one[block][v[i][2]]++;
cnt_two[block][{v[i][1], v[i][2]}]++;
}
long long ans = oo;
auto update = [&](int x, int y) {
if(v[x][1] != v[y][1] && v[x][1] != v[y][2] && v[x][2] != v[y][1] && v[x][2] != v[y][2]) {
ans = min(ans, v[x][0] + v[y][0]);
return true;
}
return false;
};
auto check_block = [&](int block, int i) {
bool found = 0;
int count = cnt_one[block][v[i][1]] + cnt_one[block][v[i][2]] - cnt_two[block][{v[i][1], v[i][2]}];
if(count != BLOCK_SIZE) {
for(int x = block * BLOCK_SIZE; !found && x < (block+1) * BLOCK_SIZE && x < (int)v.size(); ++x) {
found |= update(i, x);
}
}
return found;
};
for(int i = 0; i < (int)v.size(); ++i) {
int cur_block = i / BLOCK_SIZE;
bool found = 0;
for(int block = 0; !found && block < cur_block; ++block) {
found = check_block(block, i);
}
if(!found) {
check_block(cur_block, i);
}
}
cout << ans << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
706 ms |
98488 KB |
Output is correct |
| 2 |
Runtime error |
2706 ms |
1048580 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
706 ms |
98488 KB |
Output is correct |
| 2 |
Runtime error |
2706 ms |
1048580 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
782 ms |
97836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
706 ms |
98488 KB |
Output is correct |
| 2 |
Runtime error |
2706 ms |
1048580 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
