#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
//#include "crocodile.h"
using namespace std;
vector <pair<int,int > > adj[100000];
ll IN[100000][2];
bool vis[100000];
int Ein[100000],v,x;
ll dis[100000],d;
ll val;
struct cmp{
bool operator() (const int &a, const int &b) const {
if (Ein[a] >= 2 && Ein[b] >= 2)
return dis[a] <= dis[b];
return (Ein[a] < 2);
}
};
long long travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
for (int i = 0; i < M; i++) {
adj[ R[i][0] ].push_back( { L [i], R[i][1] } );
adj[ R[i][1] ].push_back( { L[i] , R[i][0] });
}
fill(dis,dis + 100000,100000000000000);
set<int,cmp> s;
for (int i = 0; i < K; i++)
Ein[P[i]] = 2,dis[P[i]] = 0,s.insert (P[i]);
while (!s.empty()) {
v = *s.begin();
if (Ein[v] < 2) break;
s.erase(s.begin());
if (vis[v]) continue;
vis[v] = 1;
for (auto i : adj[v]) {
x = i.se;
if (vis[x]) continue;
s.erase(x);
d = i.fi + dis[v];
if (IN[x][0] == 0) IN[x][0] = d;
else if (IN[x][1] == 0) {
IN[x][1] = d;
if (IN[x][0] > IN[x][1]) swap(IN[x][0],IN[x][1]);
}
else if (IN[x][1] > d) {
IN[x][1] = d;
if (IN[x][0] > IN[x][1]) swap(IN[x][0],IN[x][1]);
}
Ein[x] ++;
if (IN[x][1] && dis[x] > IN[x][1]) {
dis[x] = IN[x][1];
}
s.insert (x);
}
}
return dis[0];
} /*
main() { int n,m,k;
cin >> n >> m >> k;
int R[m][2],L[m]; for(int i = 0; i < m ; i++ )cin >> R[i][0] >> R[i][1] >> L[i];
int P[k]; for (int i = 0 ; i < k ; i++) cin >> P[i];
cout << travel_plan(n,m,R,L,k,P);
} */
/* 5 4 3
0 1 2
0 2 3
3 2 1
2 4 4
1 3 4
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
3456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
3456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
3456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
