#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9+7;
const int MAXN = 1e5+7;
vector<pair<int,int> > g[MAXN];
queue<pair<int,int> > kp;
int d[MAXN][2]; bool visited[MAXN];
int travel_plan(int N,int M,int R[][2],int L[],int K,int P[]){
for(int i=0;i<M;i++){
g[R[i][0]].push_back({R[i][1], L[i]});
g[R[i][1]].push_back({R[i][0], L[i]});
}
for(int i=0;i<N;i++) d[i][0]=d[i][1]=INF;
for(int i=0;i<K;i++){
d[P[i]][0]=d[P[i]][1]=0;
kp.push({0,P[i]});
}
//for(int i=0;i<N;i++) cout<<i<<' '<<d[i][0]<<' '<<d[i][1]<<'\n';
while(!kp.empty()){
int x=kp.front().second;
kp.pop();
if(visited[x]) continue;
visited[x]=1;
//cout<<"x="<<x<<'\n';
for(auto s:g[x]){
if(d[s.first][0]>d[s.first][1]) swap(d[s.first][0],d[s.first][1]);
if(max(d[x][0],d[x][1])+s.second<d[s.first][1]){
d[s.first][1]=min(INF, max(d[x][0],d[x][1])+s.second);
if(max(d[s.first][0],d[s.first][1])<INF) kp.push({max(d[s.first][1], d[s.first][0]),s.first});
}
}
}
return max(d[0][0],d[0][1]);
}/*
int main(){
int n,m,k;
int R[100][2], L[100], P[100];
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>R[i-1][0]>>R[i-1][1]>>L[i-1];
cin>>k;
for(int i=0;i<k;i++) cin>>P[i];
cout<<travel_plan(n,m,R,L,k,P)<<'\n';
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
