#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int inf = 1e9;
const int mod = 1e9+7;
const int maxn = 1e5 + 1;
#include "crocodile.h"
int dst[maxn][2];
vt<pii> g[maxn];
int travel_plan(int n, int m, int adj[][2], int l[], int k, int p[]){
for(int i = 0; i < m; i++){
g[adj[i][0]].pb({adj[i][1], l[i]});
g[adj[i][1]].pb({adj[i][0], l[i]});
}
for(int i = 0; i < n; i++){
dst[i][0] = dst[i][1] = inf;
}
priority_queue<pii, vt<pii>, greater<pii>> pq;
for(int i = 0; i < k; i++){
dst[p[i]][0] = dst[p[i]][1] = 0;
pq.push({0, p[i]});
}
while(!pq.empty()){
pii nw = pq.top();
pq.pop();
if(dst[nw.ss][1] != nw.ff)continue;
for(auto i : g[nw.ss]){
if(nw.ff + i.ss >= dst[i.ff][1])continue;
if(nw.ff + i.ss < dst[i.ff][0]){
dst[i.ff][1] = dst[i.ff][0];
dst[i.ff][0] = nw.ff + i.ss;
}
else dst[i.ff][1] = nw.ff + i.ss;
pq.push({dst[i.ff][1], i.ff});
}
}
return dst[0][1];
}
//void solve() {
//int n, m, k;
//cin >> n >> m >> k;
//int r[m][2], l[m], p[k];
//for(int i = 0; i < m; i++){
//cin >> r[i][0] >> r[i][1] >> l[i];
//}
//for(int i = 0; i < k; i++)cin >> p[i];
//cout << travel_plan(n, m, r, l, k, p);
//}
//int main() {
//ios_base::sync_with_stdio(0);
//cin.tie(0);
//int times = 1;
////cin >> times;
//for(int i = 1; i <= times; i++) {
//solve();
//}
//return 0;
//}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 4 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 5 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 6 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 7 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 8 |
Correct |
2 ms |
6828 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 4 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 5 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 6 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 7 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 8 |
Correct |
2 ms |
6828 KB |
Output is correct |
| 9 |
Correct |
3 ms |
6748 KB |
Output is correct |
| 10 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 11 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 12 |
Correct |
4 ms |
7004 KB |
Output is correct |
| 13 |
Correct |
4 ms |
7028 KB |
Output is correct |
| 14 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 15 |
Correct |
2 ms |
6748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 4 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 5 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 6 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 7 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 8 |
Correct |
2 ms |
6828 KB |
Output is correct |
| 9 |
Correct |
3 ms |
6748 KB |
Output is correct |
| 10 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 11 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 12 |
Correct |
4 ms |
7004 KB |
Output is correct |
| 13 |
Correct |
4 ms |
7028 KB |
Output is correct |
| 14 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 15 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 16 |
Correct |
307 ms |
46484 KB |
Output is correct |
| 17 |
Correct |
67 ms |
14540 KB |
Output is correct |
| 18 |
Correct |
80 ms |
15848 KB |
Output is correct |
| 19 |
Correct |
436 ms |
52320 KB |
Output is correct |
| 20 |
Correct |
205 ms |
41072 KB |
Output is correct |
| 21 |
Correct |
32 ms |
9432 KB |
Output is correct |
| 22 |
Incorrect |
232 ms |
37992 KB |
Output isn't correct |
| 23 |
Halted |
0 ms |
0 KB |
- |
