#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int N=1e5+50;
const ll inf=1e18;
vector<pair<int,ll> >E[N];
map<pair<int,int>,bool>mapa;
map<pair<int,int>,ll>grana;
bool nesto[N];
int travel_plan(int n, int m, int R[][2], int L[], int K, int P[])
{
for(int i=0;i<m;i++){
E[R[i][0]].pb({R[i][1],L[i]}),E[R[i][1]].pb({R[i][0],L[i]});
grana[{R[i][0],R[i][1]}]=grana[{R[i][1],R[i][0]}]=L[i];
}
for(int i=0;i<K;i++) nesto[P[i]]=true;
int U=0;int res=0;
while(!nesto[U]){
//printf("%i\n",U);
ll dist[n+10];int parent[n+10];
memset(parent,-1,sizeof(parent));
for(int i=0;i<n;i++) dist[i]=inf;
dist[U]=0;
priority_queue<pair<ll,int> >pq;
pq.push({0,U});
while(!pq.empty()){
int u=pq.top().se;ll w=-pq.top().fi;
pq.pop();
if(w>dist[u]) continue;
for(auto i:E[u]){
if(mapa[{i.fi,u}]) continue;
if(dist[i.fi]>dist[u]+i.se){
dist[i.fi]=dist[u]+i.se;
parent[i.fi]=u;
pq.push({-dist[i.fi],i.fi});
}
}
}
/*for(int i=0;i<n;i++) printf("%i: %i %i\n",i,dist[i],parent[i]);
printf("\n");*/
int mn=0;
for(int i=0;i<K;i++) if(dist[P[i]]<dist[P[mn]]) mn=i;
int tmp=mn;mn=P[mn];
//printf("%i %i\n",tmp,mn);
while(parent[mn]!=U) mn=parent[mn];
mapa[{U,mn}]=mapa[{mn,U}]=true;
mn=0;if(tmp==0) mn=K-1;
for(int i=0;i<K;i++) if(dist[P[i]]<dist[P[mn]] && i!=tmp) mn=i;
mn=P[mn];
while(parent[mn]!=U) mn=parent[mn];
mapa[{U,mn}]=mapa[{mn,U}]=true;
res+=grana[{U,mn}];
U=mn;
//printf("%i\n",mn);
}
return res;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
