#include<bits/stdc++.h>
using namespace std;
using int64 = int64_t;
#define REP(i, n) for(int i = 0, _n = n; i < _n; ++i)
#define REPD(i, n) for(int i = n - 1; i >= 0; --i)
#define FOR(i, l, r) for(int i = l, _r = r; i <= _r; ++i)
#define FORD(i, r, l) for(int i = r, _l = l; i >= _l; --i)
#define left __left
#define right __right
#define prev __prev
#define next __next
#define div __div
#define pb push_back
#define pf push_front
#define sz(v) (int)v.size()
#define range(v) begin(v), end(v)
#define compact(v) v.erase(unique(range(v)), end(v))
#define debug(v) "[" #v " = " << (v) << "]"
template<typename T>
bool minimize(T& a, const T& b){
if(a > b){
a = b;
return true;
}
return false;
}
template<typename T>
bool maximize(T& a, const T& b){
if(a < b){
a = b;
return true;
}
return false;
}
template<int dimension, class T>
struct vec : public vector<vec<dimension - 1, T>> {
static_assert(dimension > 0, "Dimension must be positive !\n");
template<typename... Args>
vec(int n = 0, Args... args) : vector<vec<dimension - 1, T>>(n, vec<dimension - 1, T>(args...)) {}
};
template<class T>
struct vec<1, T> : public vector<T> {
vec(int n = 0, T val = T()) : vector<T>(n, val) {}
};
int travel_plan(int n, int m, int R[][2], int L[], int k, int P[]){
vector<vector<pair<int, int>>> adj(n);
REP(i, m){
int u = R[i][0], v = R[i][1], w = L[i];
adj[u].pb(make_pair(v, w));
adj[v].pb(make_pair(u, w));
}
priority_queue<pair<int64, int>, vector<pair<int64, int>>, greater<pair<int64, int>>> pq;
vector<int64> best(n, LLONG_MAX), second_best(n, LLONG_MAX);
REP(i, k){
best[P[i]] = 0;
second_best[P[i]] = 0;
pq.push({0, P[i]});
}
vector<bool> mark(n);
while(!pq.empty()){
int64 cost;
int u;
tie(cost, u) = pq.top(); pq.pop();
if(mark[u]) continue;
for(auto [v, w] : adj[u]){
if(second_best[u] + w < second_best[v]){
second_best[v] = second_best[u] + w;
if(best[v] > second_best[v]) swap(best[v], second_best[v]);
if(second_best[v] != LLONG_MAX) pq.push(make_pair(second_best[v], v));
}
}
}
return (int)second_best[0];
}
//#define Zero_OP //turn off when submitting
#ifdef Zero_OP
void init(void);
void process(void);
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#define task "antuvu"
if(fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int T = 1; //cin >> T;
while(T--) {
init();
process();
}
return 0;
}
void init(){
}
void process(){
int R[4][2]; R[0][0] = 0; R[0][1] = 1; R[1][0] = 0; R[1][1] = 2; R[2][0] = 3; R[2][1] = 2; R[3][0] = 2; R[3][1] = 4;
int L[4]; L[0] = 2; L[1] = 3; L[2] = 1; L[3] = 4;
int P[3]; P[0] = 1; P[1] = 3; P[2] = 4;
cout << travel_plan(5, 4, R, L, 3, P);
}
#endif
Compilation message
crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:77:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
77 | for(auto [v, w] : adj[u]){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
