#include "crocodile.h"
#include<bits/stdc++.h>
#define lcm(a,b) (a/__gcd(a,b))*b
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define F first
#define S second
using namespace std;
vector<vector<pair<int,int> > >G;
const int INF=2*1e9;
int dp[1005];
void dfs(int nodo,int p){
vi v;
for(auto it : G[nodo]){
if(it.F==p)continue;
dfs(it.F,nodo);
v.pb(dp[it.F]+it.S);
}
sort(v.begin(),v.end());
if(G[nodo].size()==1){
dp[nodo]=0;
}else{
dp[nodo]=v[1];
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
//R[i][0] --- R[i][1] con peso L[i]
G.assign(N+1,vector<pair<int,int> >());
int dis[N+1][2];
for(int i=0;i<=N;i++){
dis[i][0]=dis[i][1]=INF;
}
for(int i=0;i<M;i++){
int a=R[i][0],b=R[i][1],w=L[i];
G[a].pb({b,w});
G[b].pb({a,w});
}
priority_queue<pair<int,int> >q;
for(int i=0;i<K;i++){
q.push({0,P[i]});
}
vector<bool>vis(N+1,false);
while(!q.empty()){
int nodo=q.top().S;
q.pop();
if(vis[nodo])continue;
vis[nodo]=1;
for(auto it : G[nodo]){
int D=dis[nodo][1];
if(D+it.S<dis[it.F][0]){
dis[it.F][1]=dis[it.F][0];
dis[it.F][0]=D+it.S;
if(dis[it.F][1]!=INF){
q.push({-dis[it.F][1],it.F});
}
}else{
if(D+it.S<dis[it.F][1]){
dis[it.F][1]=D+it.S;
q.push({-dis[it.F][1],it.F});
}
}
}
}
return dis[0][1];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
