#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);
queue<int> q;
for(int i = 1; i < n; i++) if(g[i].size() <= 2 && !lst[i]){
q.push(i);
proc[i] = 1;
}
while(q.size()){
int v = q.front(); q.pop();
for(int e: g[v]){
eban[e] = 1;
int u = edges[e].oth(v);
deg[u]--;
if(deg[u] <= 2 && !proc[u] && u && !lst[u]){
q.push(u);
proc[u] = 1;
}
}
}
while(true){
vector<int> dist(n, 2e9), par(n);
dist[0] = 0;
priority_queue<pair<int,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);
}
}
}
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
