#include <bits/stdc++.h>
using namespace std;using f64 = double;using i64=long long;using u64=unsigned long long;
template<typename T> using Arr=vector<T>;
#define hfor(v, s, e) for(int v=(s);(s)<=v&&v<(e);++v)//half-opened range
#define hfori(v, s, e) for(int v=(e)-1;(s)<=v&&v<(e);--v)//inversion
#define hforo(v, s, e) int v=(s);for(;(s)<=v&&v<(e);++v)//out declaration
#define hforoi(v, s, e) int v=(e)-1; for(;(s)<=v&&v<(e);--v)
#define cfor(v, s, e) hfor(v,(s),(e)+1)//closed range
#define cfori(v, s, e) hfori(v,(s),(e)+1)
#define cforo(v, s, e) hforo(v,(s),(e)+1)
#define cforoi(v, s, e) hforoi(v,(s),(e)+1)
#define rep(v,x) hfor(v,0,(x))
#define repi(v,x) hfori(v,0,(x))
#define repo(v,x) hforo(v,0,(x))
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define pushb push_back
#define pushf push_front
#define popb pop_back
#define popf pop_front
#define empl emplace
#define emplb emplace_back
#define emplf emplace_front
#define fi first
#define se second
#define cxp constexpr
#define PQ std::priority_queue
#ifndef DEBUG
#pragma GCC optimize ("Ofast")
auto __PRE_RUN__=(ios::sync_with_stdio(0), cin.tie(0), cout.tie(0),(cout<<fixed<<setprecision(11)), 0);
#endif
template<typename T> cxp T inf() { return numeric_limits<T>::max() / 2; }
auto mapf(auto a, auto f){for(auto& x:a)x=f(x); return a;}
int rd(int lb, int ub){static mt19937 rng(time(0)^i64(new int)); return uniform_int_distribution<int>(lb, ub-1)(rng);}
int rd(int ub=inf<int>()){return rd(0,ub);}
const f64 pi=acosl(-1);
#define endl '\n'//not interactive?
//#define int i64//MLE?
using pint = pair<int,int>;
using tint = tuple<int,int,int>;
int travel_plan(int n, int m, int R[][2], int L[], int k, int P[]){
Arr<pint> g[n];
rep(i,m){
int a=R[i][0], b=R[i][1], c=L[i];
g[a].pushb({b,c});
g[b].pushb({a,c});
}
PQ<pint,Arr<pint>,greater<pint>> pq;
PQ<int> dist[n];
rep(i,n)
rep(j,2)
dist[i].push(inf<int>());
rep(i,k){
int v=P[i];
dist[v].push(0);
while(sz(dist[v])>1)
dist[v].pop();
pq.push({0,v});
}
while(sz(pq)){
auto [d,v]=pq.top();
pq.pop();
if(d != dist[v].top())
continue;
for(auto i:g[v])
if(dist[i.fi].empty() or dist[i.fi].top() > d+i.se){
dist[i.fi].push(d+i.se);
while(sz(dist[i.fi])>2)
dist[i.fi].pop();
pq.push({d+i.se,i.fi});
}
}
cout<<dist[0].top()<<endl;
}
Compilation message
crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:78:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
