oj.uz

답안 #121087

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
121087 2019-06-26T05:25:59 Z turbat 악어의 지하 도시 (IOI11_crocodile) C++14
0 / 100
 4 ms 2688 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

vector <pair <int , int> > edg[100005];

bool vis[100005][2];
long long dist[100005][2];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
	for (int i = 0;i < N;i++) 
		dist[i][0] = dist[i][1] = 2e9;
	for (int i = 0;i < M;i++) {
		edg[R[i][0]].push_back(make_pair(R[i][1], L[i]));
		edg[R[i][1]].push_back(make_pair(R[i][0], L[i]));
	}
	priority_queue <pair <long long, int> > que;
	for (int i = 0;i < K;i++){
		que.push(make_pair(0, P[i]));
		vis[P[i]][0] = 1;
		dist[P[i]][0] = dist[P[i]][1] = 0;
	}
	while (!que.empty()){
		int u = que.top().second;
		long long cost = -que.top().first;
		if (vis[u][0]){
			vis[u][1] = 1;
			for (auto v : edg[u]){
				if (!vis[v.first][0] && dist[v.first][0] > cost + v.second){
					dist[v.first][0] = cost + v.second;
					que.push(make_pair(-dist[v.first][0], v.first));
				}
				else if (!vis[v.first][1] && dist[v.first][1] > cost + v.second){
					dist[v.first][1] = cost + v.second;
					que.push(make_pair(-dist[v.first][1], v.first));
				}
			}
		}
		else vis[u][0] = 1;
		while (!que.empty() && vis[que.top().second][1])
			que.pop();
	}
	return dist[0][1];
}

Subtask #1
0 / 46.0

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

Subtask #2
0 / 43.0

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

Subtask #3
0 / 11.0

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