#include<bits/stdc++.h>
#define ii pair <int,int>
#define fi first
#define se second
#define int long long
#define double long double
#define endl '\n'
#define all(x) x.begin(), x.end()
using namespace std;
const int maxN = 5010;
const int inf = 1e18;
int n, m, k;
vector <ii> adj[maxN];
int spec[maxN];
int ans[maxN];
int getId[maxN];
int visited[maxN];
unordered_set <int> ban;
priority_queue <ii, vector <ii>, greater <ii>> myHeap;
bool getBit(int mask, int i){
return (mask & (1 << i));
}
void reset(){
for (int i = 1; i <= n; i++){
visited[i] = inf;
}
}
void dickcha(){
while(!myHeap.empty()){
ii tempV = myHeap.top();
// cout << tempV.se << " " << visited[tempV.se] << endl;
myHeap.pop();
if (tempV.fi != visited[tempV.se]){
continue;
}
for (auto newV: adj[tempV.se]){
if (visited[tempV.se] + newV.fi < visited[newV.se]){
// cout << newV.se << ' ';
visited[newV.se] = visited[tempV.se] + newV.fi;
myHeap.push({visited[newV.se], newV.se});
}
}
// cout << endl << endl;
}
}
void Try(){
dickcha();
for (int i = 1; i <= k; i++){
if (ban.find(spec[i]) == ban.end() and visited[spec[i]] != 0){
ans[spec[i]] = min(ans[spec[i]], visited[spec[i]]);
// cout << spec[i] << " " << visited[spec[i]] << endl;
}
}
}
int calmin(){
for (int i = 1; i <= k; i++){
ans[spec[i]] = inf;
}
for (int j = log2(k); j >= 0; j--){
// cout << "Try: " << endl;
reset();
for (int i = 1; i <= k; i++){
if (getBit(i,j) and ban.find(spec[i]) == ban.end()){
myHeap.push({0,spec[i]});
visited[spec[i]] = 0;
// cout << spec[i] << " ";
}
}
// cout << endl;
Try();
// cout << "Try: " << endl;
reset();
for (int i = 1; i <= k; i++){
if (!getBit(i,j) and ban.find(spec[i]) == ban.end()){
myHeap.push({0,spec[i]});
visited[spec[i]] = 0;
// cout << spec[i] << " ";
}
}
// cout << endl;
Try();
}
int res = inf;
for (int i = 1; i <= k; i++){
if (ban.find(spec[i]) == ban.end()){
res = min(res, ans[spec[i]]);
// cout << spec[i] << " " << ans[spec[i]] << endl;
}
}
return res;
}
vector <ii> lists;
signed main(){
//freopen("input.INP", "r", stdin);
//freopen("output.OUT", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m >> k;
for (int i = 1; i <= m; i++){
int a, b, w;
cin >> a >> b >> w;
// cout << a << " " << b << " " << w << endl;
adj[a].push_back({w,b});
adj[b].push_back({w,a});
}
for (int i = 1; i <= k; i++){
cin >> spec[i];
}
int res = inf;
for (int i = 1; i <= k; i++){
reset();
myHeap.push({0,spec[i]});
visited[spec[i]] = 0;
dickcha();
lists.clear();
for (int j = i + 1; j <= k; j++){
lists.push_back({visited[spec[j]],spec[j]});
// cout << spec[i] << " " << spec[j] << ": " << visited[spec[j]] << endl;
}
ban.insert(spec[i]);
sort(all(lists));
for (auto j: lists){
if (res <= j.fi){
break;
}
ban.insert(j.se);
// cout << spec[i] << "-" << j.se << endl;
// cout << j.fi << " " << calmin() << endl;
res = min(res,j.fi + calmin());
ban.erase(j.se);
}
}
cout << res << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
2 ms |
468 KB |
Output is correct |
8 |
Correct |
2 ms |
468 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
2 ms |
468 KB |
Output is correct |
14 |
Correct |
1 ms |
468 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
468 KB |
Output is correct |
17 |
Correct |
2 ms |
512 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
2 ms |
468 KB |
Output is correct |
20 |
Correct |
1 ms |
468 KB |
Output is correct |
21 |
Correct |
2 ms |
468 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
2 ms |
468 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
0 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
2 ms |
468 KB |
Output is correct |
29 |
Correct |
2 ms |
468 KB |
Output is correct |
30 |
Correct |
2 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
2 ms |
468 KB |
Output is correct |
8 |
Correct |
2 ms |
468 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
2 ms |
468 KB |
Output is correct |
14 |
Correct |
1 ms |
468 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
468 KB |
Output is correct |
17 |
Correct |
2 ms |
512 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
2 ms |
468 KB |
Output is correct |
20 |
Correct |
1 ms |
468 KB |
Output is correct |
21 |
Correct |
2 ms |
468 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
2 ms |
468 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
0 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
2 ms |
468 KB |
Output is correct |
29 |
Correct |
2 ms |
468 KB |
Output is correct |
30 |
Correct |
2 ms |
468 KB |
Output is correct |
31 |
Correct |
1 ms |
468 KB |
Output is correct |
32 |
Correct |
2 ms |
468 KB |
Output is correct |
33 |
Correct |
3 ms |
468 KB |
Output is correct |
34 |
Correct |
1 ms |
468 KB |
Output is correct |
35 |
Correct |
0 ms |
340 KB |
Output is correct |
36 |
Correct |
57 ms |
724 KB |
Output is correct |
37 |
Correct |
111 ms |
820 KB |
Output is correct |
38 |
Correct |
4 ms |
468 KB |
Output is correct |
39 |
Correct |
71 ms |
4948 KB |
Output is correct |
40 |
Correct |
102 ms |
1620 KB |
Output is correct |
41 |
Correct |
9 ms |
468 KB |
Output is correct |
42 |
Correct |
124 ms |
1560 KB |
Output is correct |
43 |
Correct |
50 ms |
652 KB |
Output is correct |
44 |
Correct |
4 ms |
468 KB |
Output is correct |
45 |
Correct |
1 ms |
468 KB |
Output is correct |
46 |
Correct |
747 ms |
5196 KB |
Output is correct |
47 |
Correct |
124 ms |
1108 KB |
Output is correct |
48 |
Correct |
105 ms |
5012 KB |
Output is correct |
49 |
Correct |
315 ms |
4948 KB |
Output is correct |
50 |
Correct |
6 ms |
468 KB |
Output is correct |
51 |
Correct |
28 ms |
552 KB |
Output is correct |
52 |
Correct |
15 ms |
500 KB |
Output is correct |
53 |
Correct |
60 ms |
2748 KB |
Output is correct |
54 |
Correct |
81 ms |
5032 KB |
Output is correct |
55 |
Correct |
2 ms |
468 KB |
Output is correct |
56 |
Correct |
1 ms |
468 KB |
Output is correct |
57 |
Correct |
3 ms |
468 KB |
Output is correct |
58 |
Correct |
239 ms |
5060 KB |
Output is correct |
59 |
Correct |
0 ms |
340 KB |
Output is correct |
60 |
Correct |
37 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
724 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
2 ms |
468 KB |
Output is correct |
8 |
Correct |
2 ms |
468 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
2 ms |
468 KB |
Output is correct |
14 |
Correct |
1 ms |
468 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
468 KB |
Output is correct |
17 |
Correct |
2 ms |
512 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
2 ms |
468 KB |
Output is correct |
20 |
Correct |
1 ms |
468 KB |
Output is correct |
21 |
Correct |
2 ms |
468 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
2 ms |
468 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
0 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
2 ms |
468 KB |
Output is correct |
29 |
Correct |
2 ms |
468 KB |
Output is correct |
30 |
Correct |
2 ms |
468 KB |
Output is correct |
31 |
Correct |
1 ms |
468 KB |
Output is correct |
32 |
Correct |
2 ms |
468 KB |
Output is correct |
33 |
Correct |
3 ms |
468 KB |
Output is correct |
34 |
Correct |
1 ms |
468 KB |
Output is correct |
35 |
Correct |
0 ms |
340 KB |
Output is correct |
36 |
Correct |
57 ms |
724 KB |
Output is correct |
37 |
Correct |
111 ms |
820 KB |
Output is correct |
38 |
Correct |
4 ms |
468 KB |
Output is correct |
39 |
Correct |
71 ms |
4948 KB |
Output is correct |
40 |
Correct |
102 ms |
1620 KB |
Output is correct |
41 |
Correct |
9 ms |
468 KB |
Output is correct |
42 |
Correct |
124 ms |
1560 KB |
Output is correct |
43 |
Correct |
50 ms |
652 KB |
Output is correct |
44 |
Correct |
4 ms |
468 KB |
Output is correct |
45 |
Correct |
1 ms |
468 KB |
Output is correct |
46 |
Correct |
747 ms |
5196 KB |
Output is correct |
47 |
Correct |
124 ms |
1108 KB |
Output is correct |
48 |
Correct |
105 ms |
5012 KB |
Output is correct |
49 |
Correct |
315 ms |
4948 KB |
Output is correct |
50 |
Correct |
6 ms |
468 KB |
Output is correct |
51 |
Correct |
28 ms |
552 KB |
Output is correct |
52 |
Correct |
15 ms |
500 KB |
Output is correct |
53 |
Correct |
60 ms |
2748 KB |
Output is correct |
54 |
Correct |
81 ms |
5032 KB |
Output is correct |
55 |
Correct |
2 ms |
468 KB |
Output is correct |
56 |
Correct |
1 ms |
468 KB |
Output is correct |
57 |
Correct |
3 ms |
468 KB |
Output is correct |
58 |
Correct |
239 ms |
5060 KB |
Output is correct |
59 |
Correct |
0 ms |
340 KB |
Output is correct |
60 |
Correct |
37 ms |
468 KB |
Output is correct |
61 |
Runtime error |
1 ms |
724 KB |
Execution killed with signal 11 |
62 |
Halted |
0 ms |
0 KB |
- |