oj.uz

Submission #133685

# Submission time Handle Problem Language Result Execution time Memory
133685 2019-07-21T08:31:55 Z Boxworld Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 2 ms 376 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -