#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
using ll = long long;
struct edge{
int u, v, w;
int oth(int o){
return u ^ v ^ o;
}
};
int travel_plan(int n, int m, int r[][2], int L[], int k, int p[]){
vector<int> lst(n);
for(int i = 0; i < k; i++){
lst[p[i]] = 1;
}
vector<edge> edges;
vector<vector<int>> g(n);
vector<int> deg(n);
for(int i = 0; i < m; i++){
edges.push_back({r[i][0], r[i][1], L[i]});
g[r[i][0]].push_back(i);
g[r[i][1]].push_back(i);
deg[r[i][0]]++;
deg[r[i][1]]++;
}
vector<int> eban(m), ban(n, -1), proc(n);
while(true){
vector<ll> dist(n, 1e18), par(n);
dist[0] = 0;
priority_queue<pair<ll,int>> pq;
pq.emplace(0, 0);
while(pq.size()){
auto [d, v] = pq.top(); pq.pop();
if(-d > dist[v]) continue;
if(lst[v]){
int has = 0;
while(v != 0){
int u = edges[par[v]].oth(v);
if(ban[u] == -1){
has = 1;
ban[u] = par[v];
}
eban[par[v]] = 1;
v = u;
}
if(!has) return -d;
else break;
}
for(int e: g[v]) if(!eban[e]){
int u = edges[e].oth(v);
if(dist[u] > dist[v] + edges[e].w){
dist[u] = dist[v] + edges[e].w;
par[u] = e;
pq.emplace(-dist[u], u);
}
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2062 ms |
212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2062 ms |
212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2062 ms |
212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
