#include "crocodile.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pll;
struct Edge{
int v;LL w;
Edge(){}
Edge(int v, LL w): v(v), w(w) {}
bool operator< (const Edge &rhs) const{
return w > rhs.w;
}
};
const int mxsz = 1e5 + 3;
int n, m, k;
vector<Edge> adj[mxsz];
LL d[mxsz];
pll best[mxsz];
priority_queue<Edge> pq;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
n = N, m = M, k = K;
fill(best, best+n, make_pair(1e18, 1e18));
for (int i = 0, u, v; i < m; i++){
u = R[i][0], v = R[i][1];
adj[u].emplace_back(v, L[i]);
adj[v].emplace_back(u, L[i]);
}
for (int i = 0; i < k; i++) pq.emplace(P[i], 0);
for (int i = 0; i < k; i++) best[P[i]] = make_pair(0,0);
while (!pq.empty()){
Edge e = pq.top(); pq.pop();
int u = e.v;
//cout << u << ' ' << e.w << " {" << best[u].fi << ", " << best[u].se << '}'<< '\n';
// if (e.w < best[u].se) best[u].se = e.w;
// if (best[u].fi > best[u].se) swap(best[u].fi, best[u].se);
if (best[u].se < e.w) continue;
int v; LL w;
for (Edge nx : adj[u]){
v = nx.v, w = nx.w; LL c = e.w + w;
//if (best[u].se > c){ swap(best[u].se, c); }
if (best[v].fi > c){
if (best[v].se > best[v].fi){
pq.emplace(v, best[v].fi);
}
swap(best[v].fi, best[v].se);
best[v].fi = c;
} else if (best[v].se > c){
pq.emplace(v, (best[v].se = c) );
}
}
}
LL ret = best[0].se;
return (ret >= 1e18 ? -1 : ret);
return n;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 7 |
Correct |
5 ms |
2816 KB |
Output is correct |
| 8 |
Correct |
4 ms |
2816 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 7 |
Correct |
5 ms |
2816 KB |
Output is correct |
| 8 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 9 |
Correct |
6 ms |
3072 KB |
Output is correct |
| 10 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 11 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 12 |
Correct |
7 ms |
3456 KB |
Output is correct |
| 13 |
Correct |
7 ms |
3456 KB |
Output is correct |
| 14 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 15 |
Correct |
4 ms |
2816 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 7 |
Correct |
5 ms |
2816 KB |
Output is correct |
| 8 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 9 |
Correct |
6 ms |
3072 KB |
Output is correct |
| 10 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 11 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 12 |
Correct |
7 ms |
3456 KB |
Output is correct |
| 13 |
Correct |
7 ms |
3456 KB |
Output is correct |
| 14 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 15 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 16 |
Correct |
594 ms |
66696 KB |
Output is correct |
| 17 |
Correct |
86 ms |
14584 KB |
Output is correct |
| 18 |
Correct |
132 ms |
16868 KB |
Output is correct |
| 19 |
Correct |
798 ms |
73196 KB |
Output is correct |
| 20 |
Correct |
344 ms |
54624 KB |
Output is correct |
| 21 |
Correct |
47 ms |
8568 KB |
Output is correct |
| 22 |
Correct |
348 ms |
50124 KB |
Output is correct |
