This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "crocodile.h"
#include <vector>
#define INF 1000000000
#define MAXN 100000
struct myc {
int best, next;
inline bool operator < (const myc &u) const {
return next < u.next;
}
} d[MAXN];
struct mom {
int x, y;
};
std::vector < mom > g[MAXN];
int heap[MAXN + 1], poz[MAXN];
bool done[MAXN];
inline void mySwap(int p, int q) {
int aux = heap[p];
heap[p] = heap[q];
heap[q] = aux;
poz[heap[p]] = p;
poz[heap[q]] = q;
}
inline void urcare(int p) {
while (p > 1 && d[heap[p]] < d[heap[p / 2]]) {
mySwap(p, p / 2);
p /= 2;
}
}
inline void coborare(int p) {
int q;
bool f = 1;
while (f && (q = 2 * p) <= heap[0]) {
if (q < heap[0] && d[heap[q + 1]] < d[heap[q]])
q++;
if (d[heap[q]] < d[heap[p]]) {
mySwap(p, q);
p = q;
} else
f = 0;
}
}
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] = {INF, INF}, done[i] = 0;
for (int i = 0; i < K; i++) d[P[i]] = {0, 0};
for (int i = 0; i < N; i++) heap[i + 1] = i, poz[i] = i + 1;
heap[0] = N;
for (int i = N; i > 0; i--)
coborare(i);
while (heap[1] != 0) {
int x = heap[1];
done[x] = 1;
for (auto &y : g[x]) {
if (done[y.x] == 0) {
long long val = d[x].next + y.y;
if (val < d[y.x].next) {
if (val < d[y.x].best) {
d[y.x].next = d[y.x].best;
d[y.x].best = val;
} else
d[y.x].next = val;
urcare(poz[y.x]);
}
}
}
d[x] = {INF, INF};
coborare(1);
}
return d[0].next;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |