#include <bits/stdc++.h>
using namespace std;
int const MN=1e5+5;
int const inf=1e9+5;
vector<pair<int,int>> adj[MN];
int maxa[MN],secmaxa[MN];
bool ex[MN];
set<pair<int,int>> d;
void dijikstra(){
while(d.size()){
auto p=d.begin();
int dis=(*p).first;
int node=(*p).second;
// cerr<<node<<' '<<dis<<endl;
d.erase(p);
if(node==0)
continue;
for(auto i:adj[node]){
int di=dis+i.second;
if(di>=secmaxa[i.first])
continue;
d.erase({secmaxa[i.first],i.first});
if(di<maxa[i.first]){
secmaxa[i.first]=maxa[i.first];
maxa[i.first]=di;
}
else
secmaxa[i.first]=di;
d.insert({secmaxa[i.first],i.first});
}
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
for (int i = 0; i < M; ++i)
{
int u=R[i][0];
int v=R[i][1];
adj[u].push_back({v,L[i]});
adj[v].push_back({u,L[i]});
}
for (int i = 0; i < N; ++i)
maxa[i]=inf,secmaxa[i]=inf;
for (int i = 0; i < K; ++i)
{
maxa[P[i]]=0;
secmaxa[P[i]]=0;
d.insert({0,P[i]});
}
dijikstra();
// cout<<"return"<<endl;
return secmaxa[0];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
2 ms |
6488 KB |
Output is correct |
4 |
Correct |
2 ms |
6488 KB |
Output is correct |
5 |
Correct |
2 ms |
6488 KB |
Output is correct |
6 |
Correct |
2 ms |
6492 KB |
Output is correct |
7 |
Correct |
2 ms |
6492 KB |
Output is correct |
8 |
Correct |
2 ms |
6492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
2 ms |
6488 KB |
Output is correct |
4 |
Correct |
2 ms |
6488 KB |
Output is correct |
5 |
Correct |
2 ms |
6488 KB |
Output is correct |
6 |
Correct |
2 ms |
6492 KB |
Output is correct |
7 |
Correct |
2 ms |
6492 KB |
Output is correct |
8 |
Correct |
2 ms |
6492 KB |
Output is correct |
9 |
Correct |
3 ms |
6744 KB |
Output is correct |
10 |
Correct |
1 ms |
6488 KB |
Output is correct |
11 |
Correct |
4 ms |
6488 KB |
Output is correct |
12 |
Correct |
4 ms |
6748 KB |
Output is correct |
13 |
Correct |
4 ms |
6956 KB |
Output is correct |
14 |
Correct |
1 ms |
6604 KB |
Output is correct |
15 |
Correct |
2 ms |
6492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
2 ms |
6488 KB |
Output is correct |
4 |
Correct |
2 ms |
6488 KB |
Output is correct |
5 |
Correct |
2 ms |
6488 KB |
Output is correct |
6 |
Correct |
2 ms |
6492 KB |
Output is correct |
7 |
Correct |
2 ms |
6492 KB |
Output is correct |
8 |
Correct |
2 ms |
6492 KB |
Output is correct |
9 |
Correct |
3 ms |
6744 KB |
Output is correct |
10 |
Correct |
1 ms |
6488 KB |
Output is correct |
11 |
Correct |
4 ms |
6488 KB |
Output is correct |
12 |
Correct |
4 ms |
6748 KB |
Output is correct |
13 |
Correct |
4 ms |
6956 KB |
Output is correct |
14 |
Correct |
1 ms |
6604 KB |
Output is correct |
15 |
Correct |
2 ms |
6492 KB |
Output is correct |
16 |
Correct |
369 ms |
60244 KB |
Output is correct |
17 |
Correct |
59 ms |
16436 KB |
Output is correct |
18 |
Correct |
94 ms |
17952 KB |
Output is correct |
19 |
Correct |
576 ms |
63760 KB |
Output is correct |
20 |
Correct |
228 ms |
53940 KB |
Output is correct |
21 |
Correct |
33 ms |
12372 KB |
Output is correct |
22 |
Correct |
250 ms |
51488 KB |
Output is correct |