#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=100007;
ll n,m,k;
vector<pair<ll,ll>>g[N];
int used[N];
int travel_plan(int NN, int MM, int R[][2], int L[], int KK, int P[]){
n=NN;
m=MM;
k=KK;
for(ll i=0;i<m;i++){
// cout<<R[i][0]<<" "<<R[i][1]<<endl;
g[R[i][0]].push_back(make_pair(R[i][1],L[i]));
g[R[i][1]].push_back(make_pair(R[i][0],L[i]));
}
priority_queue<pii,vector<pii>,greater<pii>>q;
vector<ll>mn(n+1,INF),smn(n+1,INF);
// cout<<mn[0]<<" "<<smn[0]<<endl;
for(ll i=0;i<k;i++){
q.push(make_pair(0,P[i]));
mn[P[i]]=smn[P[i]]=0;
}
while(!q.empty()){
ll v=q.top().ss;
ll w=q.top().ff;
// cout<<v<<" "<<w<<endl;
// cout<<mn[v]<<" "<<smn[v]<<endl<<endl;
q.pop();
if(smn[v]==w){
// if(v==320){
// cout<<"Qnnarkum enq 320in: "<<w<<endl;
// }
// if(used[v])cout<<v<<": "<<used[v]<<"->"<<w<<endl;
used[v]=w;
for(pii x:g[v]){
ll to=x.ff;
ll dist=x.ss;
// cout<<v<<" "<<to<<" "<<dist<<endl;
// cout<<mn[to]<<" "<<smn[v]<<endl;
// cout<<endl;
if(mn[to]>smn[v]+dist){
// if(to==320){
// cout<<"320y yngnelu a queue-i mej (hima: "<<smn[to]<<")"<<endl;
// }
bool etas=!(smn[to]==mn[to]);
smn[to]=mn[to];
mn[to]=smn[v]+dist;
if(smn[to]!=INF&&etas)
q.push(make_pair(smn[to],to));
// if(to==320){
// cout<<"320y yngav queue-i mej 1: "<<smn[to]<<endl;
// }
}
else if(smn[to]>smn[v]+dist){
// if(to==320){
// cout<<"320y yngnelu a queue-i mej (hima: "<<smn[to]<<")"<<endl;
// }
smn[to]=smn[v]+dist;
q.push(make_pair(smn[to],to));
// if(to==320){
// cout<<"320y yngav queue-i mej 2: "<<smn[to]<<endl;
// }
}
}
}
}
return smn[0];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2668 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2772 KB |
Output is correct |
5 |
Correct |
2 ms |
2808 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
3 ms |
2772 KB |
Output is correct |
8 |
Correct |
2 ms |
2772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2668 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2772 KB |
Output is correct |
5 |
Correct |
2 ms |
2808 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
3 ms |
2772 KB |
Output is correct |
8 |
Correct |
2 ms |
2772 KB |
Output is correct |
9 |
Correct |
3 ms |
3068 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
2 ms |
2900 KB |
Output is correct |
12 |
Correct |
6 ms |
3412 KB |
Output is correct |
13 |
Correct |
4 ms |
3412 KB |
Output is correct |
14 |
Correct |
2 ms |
2644 KB |
Output is correct |
15 |
Correct |
2 ms |
2772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2668 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2772 KB |
Output is correct |
5 |
Correct |
2 ms |
2808 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
3 ms |
2772 KB |
Output is correct |
8 |
Correct |
2 ms |
2772 KB |
Output is correct |
9 |
Correct |
3 ms |
3068 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
2 ms |
2900 KB |
Output is correct |
12 |
Correct |
6 ms |
3412 KB |
Output is correct |
13 |
Correct |
4 ms |
3412 KB |
Output is correct |
14 |
Correct |
2 ms |
2644 KB |
Output is correct |
15 |
Correct |
2 ms |
2772 KB |
Output is correct |
16 |
Correct |
354 ms |
67484 KB |
Output is correct |
17 |
Correct |
56 ms |
15104 KB |
Output is correct |
18 |
Correct |
80 ms |
17436 KB |
Output is correct |
19 |
Correct |
409 ms |
73768 KB |
Output is correct |
20 |
Correct |
262 ms |
55480 KB |
Output is correct |
21 |
Correct |
28 ms |
8540 KB |
Output is correct |
22 |
Correct |
242 ms |
50592 KB |
Output is correct |