제출 #963873

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
963873		pragmatist	악어의 지하 도시 (IOI11_crocodile)	C++17	89 / 100	384 ms	68124 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;

const int N = (int)1e5+7;
const int INF = (int)1e9+7;

vector<pair<int, int> > g[N];
int n, m;
int d1[N], d2[N];

int travel_plan(int _N, int _M, int _R[][2], int _L[], int _K, int _P[]) {
	n = _N;
	m = _M;
	for(int i = 0; i < m; ++i) {
		int u = _R[i][0], v = _R[i][1], w = _L[i];
		u++;
		v++;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	for(int i = 1; i <= n; ++i) {
		d1[i] = d2[i] = INF;
	}
	priority_queue<pair<int, int> > q;
	for(int i = 0; i < _K; ++i) {
		int v = _P[i]+1;
		d1[v]=d2[v]=0;
		q.push({0, v});
	}
	while(!q.empty()) {
		int v = q.top().second;
		long long cur_d = -q.top().first;
		q.pop();
		if(cur_d>d2[v]) {
			continue;
		}
		for(auto [to, w] : g[v]) {
			if(d2[v]+w<d1[to]) {
				d2[to]=d1[to];
				d1[to]=d2[v]+w;
				q.push({-d2[to], to});				
			} else {    
				if(d2[v]+w<d2[to]) {
					d2[to]=d2[v]+w;
					q.push({-d2[to], to});				
				}
			}
		}
	}
	return d2[1];
}

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