답안 #946584

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
946584 2024-03-14T19:04:49 Z StefanSebez 악어의 지하 도시 (IOI11_crocodile) C++14
0 / 100
1 ms 6488 KB
#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 -