#include<bits/stdc++.h>
using namespace std;
#include "crocodile.h"
#define F first
#define S second
#define ll long long
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
int dist[1000000];
int par[1000000];
vector<vii> adj;
#define INF 1500000000
bool vis[1000000];
int o[1000000];
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
adj.assign(n+1, vii());
for(int i=0;i<m;i++){
adj[r[i][0]].push_back(ii(l[i], r[i][1]));
adj[r[i][1]].push_back(ii(l[i], r[i][0]));
}
for(int i=0;i<n;i++){
sort(adj[i].begin(), adj[i].end());
}
priority_queue<ii> q;
q.push(ii(0, 0));
dist[0] = 0;
for(int i=1;i<n;i++) dist[i]=INF;
while(!q.empty()){
ii t = q.top();
q.pop();
if(-t.F>dist[t.S]) continue;
//cout<<t.F<<" "<<t.S<<" "<<dist[t.S]<<endl;
for(auto v : adj[t.S]){
if(dist[v.S]> -t.F + v.F){
dist[v.S] = v.F - t.F;
par[v.S] = t.S;
q.push(ii(-dist[v.S], v.S));
}
}
}
vii d;
for(int i=0;i<k;i++){
d.push_back(ii(-dist[p[i]], p[i]));
}
for(int i=1;i<n;i++){
o[i]++;
o[par[i]]++;
}
sort(d.begin(), d.end());
for(auto x : d){
int t = par[x.S];
bool found = false;
while(par[t]!=t){
if(o[t]>3){ o[t]--; found = true; break;}
t = par[t];
}
if(!found) return -x.F;
}
return -1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
