제출 #121087

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
121087		turbat	Crocodile's Underground City (IOI11_crocodile)	C++14	0 / 100	4 ms	2688 KiB

crocodile

#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
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11