#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;
}
set<pii> pq;
for(int i = 0; i < k; i++){
dst[p[i]][0] = dst[p[i]][1] = 0;
pq.insert({0, p[i]});
}
while(!pq.empty()){
pii nw = *pq.begin();
pq.erase(pq.begin());
for(auto i : g[nw.ss]){
if(nw.ff + i.ss >= dst[i.ff][1])continue;
if(pq.find({dst[i.ff][1], i.ff}) != pq.end())pq.erase(pq.find({dst[i.ff][1], i.ff}));
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.insert({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;
//}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
6744 KB |
Output is correct |
| 2 |
Correct |
2 ms |
7000 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6796 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 |
6744 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
6744 KB |
Output is correct |
| 2 |
Correct |
2 ms |
7000 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6796 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 |
6744 KB |
Output is correct |
| 9 |
Correct |
3 ms |
6744 KB |
Output is correct |
| 10 |
Correct |
3 ms |
6748 KB |
Output is correct |
| 11 |
Correct |
3 ms |
6748 KB |
Output is correct |
| 12 |
Correct |
4 ms |
7000 KB |
Output is correct |
| 13 |
Correct |
4 ms |
7004 KB |
Output is correct |
| 14 |
Correct |
2 ms |
6744 KB |
Output is correct |
| 15 |
Correct |
3 ms |
6748 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
6744 KB |
Output is correct |
| 2 |
Correct |
2 ms |
7000 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6796 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 |
6744 KB |
Output is correct |
| 9 |
Correct |
3 ms |
6744 KB |
Output is correct |
| 10 |
Correct |
3 ms |
6748 KB |
Output is correct |
| 11 |
Correct |
3 ms |
6748 KB |
Output is correct |
| 12 |
Correct |
4 ms |
7000 KB |
Output is correct |
| 13 |
Correct |
4 ms |
7004 KB |
Output is correct |
| 14 |
Correct |
2 ms |
6744 KB |
Output is correct |
| 15 |
Correct |
3 ms |
6748 KB |
Output is correct |
| 16 |
Correct |
385 ms |
52552 KB |
Output is correct |
| 17 |
Correct |
62 ms |
15212 KB |
Output is correct |
| 18 |
Correct |
101 ms |
16736 KB |
Output is correct |
| 19 |
Correct |
652 ms |
55996 KB |
Output is correct |
| 20 |
Correct |
214 ms |
47908 KB |
Output is correct |
| 21 |
Correct |
34 ms |
10064 KB |
Output is correct |
| 22 |
Correct |
251 ms |
44648 KB |
Output is correct |
