oj.uz

답안 #70010

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
70010 2018-08-22T08:59:05 Z nvmdava 악어의 지하 도시 (IOI11_crocodile) C++17
0 / 100
 6 ms 3068 KB 
#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;

struct Chamber{
	int cost, id, from;
	Chamber(int from, int id, int cost){
		this -> from = from;
		this -> id = id;
		this -> cost = cost;
	}
	
	bool operator<(const Chamber& rhs) const {
		return cost > rhs.cost;
	}
};

struct Path{
	int to, cost;
	Path(int to, int cost){
		this -> to = to;
		this -> cost = cost;
	}
};

priority_queue<Chamber> pq;
vector<Path> p[100001];
int block[100001];
int ans[100001];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
	for(int i = 0; i < M ; i++){
		p[R[i][0]].push_back(Path(R[i][1], L[i]));
		p[R[i][1]].push_back(Path(R[i][0], L[i]));
	}
	memset(ans, -1, sizeof(ans));
	for(int i = 0; i < K; i++){
		pq.push(Chamber(-1, P[i], 0));
	}
	int v;
	while(!pq.empty()){
		v = pq.top().id;
		if(ans[v] != -1){
			pq.pop();
			continue;
		}
		
		ans[v] = pq.top().cost;
		block[v] = pq.top().from;
		
		for(auto x : p[v]){
			if(ans[x.to] != -1) continue;
			pq.push(Chamber(v, x.to, ans[v] + x.cost));
		}
	}
	
	memset(ans, -1, sizeof(ans));
	pq.push(Chamber(0, 0, 0));
	while(!pq.empty()){
		v = pq.top().id;
		if(ans[v] != -1){
			pq.pop();
			continue;
		}
		ans[v] = pq.top().cost;
		if(block[v] == -1){
			return ans[v];
		}
		for(auto x : p[v]){
			if(x.to == block[v]) continue;
			if(ans[x.to] != -1) continue;
			pq.push(Chamber(0, x.to, ans[v] + x.cost));
		}
	}
}

/*
#define MAX_N 50000
#define MAX_M 10000000

static int N, M;
static int R[MAX_M][2];
static int L[MAX_M];
static int K;
static int P[MAX_N];
static int solution;

inline 
void my_assert(int e) {if (!e) abort();}

void read_input()
{
  int i;
  my_assert(3==scanf("%d %d %d",&N,&M,&K));
  for(i=0; i<M; i++)
    my_assert(3==scanf("%d %d %d",&R[i][0],&R[i][1],&L[i]));
  for(i=0; i<K; i++)
    my_assert(1==scanf("%d",&P[i]));
  my_assert(1==scanf("%d",&solution));
}

int main()
{
  int ans;
  read_input();
  ans = travel_plan(N,M,R,L,K,P);
  if(ans==solution)
    printf("Correct.\n");
  else
    printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);

  return 0;
}*/

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:74:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 3068 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 3068 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 3068 KB Output isn't correct
2 Halted 0 ms 0 KB -