제출 #1081359

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1081359		nrg_studio	악어의 지하 도시 (IOI11_crocodile)	C++17	100 / 100	327 ms	72872 KiB

crocodile

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define pii pair<ll,ll>
#define f first
#define s second
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)

ll ans;

ll travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
	ios::sync_with_stdio(false); cin.tie(0);

	vector<vector<pii>> adj(n);
	F0R(i,m) {
		adj[r[i][0]].pb({r[i][1],l[i]});
		adj[r[i][1]].pb({r[i][0],l[i]});
	}
	vector<pii> mn(n,{LLONG_MAX,LLONG_MAX});
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	F0R(i,k) {
		mn[p[i]] = {0,0};
		pq.push({0,p[i]});
	} 
	vector<bool> vis(n,false);
	while (pq.size()) {
		pii cur = pq.top(); pq.pop();
		if (vis[cur.s]) {continue;}
		vis[cur.s] = true;
		/*
		if (cur.f != mn[cur.s].s) {continue;} This line may run twice if the two minimums are the same.
		Meaning that one of its children may be updated twice from the same node, 
		which means there are two directed edges connecting the same pair of nodes,
		which doesn't follow the constraints of the escape plan.
		*/

		for (pii qwerty : adj[cur.s]) {
			ll cand = qwerty.s+cur.f, x = qwerty.f;
			if (cand < mn[x].s) {
				if (cand <= mn[x].f) {
					mn[x].s = mn[x].f; mn[x].f = cand;	
				} else {mn[x].s = cand;}
				if (mn[x].s!=LLONG_MAX) {pq.push({mn[x].s,x});}
			}
		}
	} 
	ans = mn[0].s;
	return ans;
}

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