Submission #133685

#	Time	Username	Problem	Language	Result	Execution time	Memory
133685		Boxworld	Crocodile's Underground City (IOI11_crocodile)	C++14	0 / 100	2 ms	376 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> Pa;
const int maxN=100100,inf=0x7fffffff;
struct edge{int v,d,nxt;}a[20*maxN];
int dis[maxN],head[maxN],best[maxN];
int cnt=0;
priority_queue<Pa,vector<Pa>,greater<Pa> > Q;
void add(int u,int v,int d){
	a[++cnt].v=v;
	a[cnt].d=d;
	a[cnt].nxt=head[u];
	head[u]=cnt;
	if (d<a[best[u]].d)best[u]=cnt;
//	printf("edge#%d u:%d v:%d d:%d\n",cnt,u,a[cnt].v,a[cnt].d);
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
	a[0].d=inf;
	for (int i=0;i<N;i++){best[i]=0;dis[i]=inf;head[i]=-1;}
	for (int i=0;i<M;i++){
		add(R[i][0],R[i][1],L[i]);
		add(R[i][1],R[i][0],L[i]);
	}
	dis[0]=0;
	Q.push(make_pair(0,0));
	while(!Q.empty()){
		int D=Q.top().first,u=Q.top().second;Q.pop();
		if (D>dis[u])continue;
		for (int i=head[u];i!=-1;i=a[i].nxt){
			if (i==best[u])continue;
			int v=a[i].v;
			if (dis[v]>dis[u]+a[i].d){
				dis[v]=dis[u]+a[i].d;
				Q.push(make_pair(dis[v],v));
			}
		}
	}
	int ans=inf;
	for (int i=0;i<K;i++)ans=min(ans,dis[P[i]]);
	return ans;
}


 

• Subtask 1: 0 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11