제출 #1081358

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1081358		nrg_studio	악어의 지하 도시 (IOI11_crocodile)	C++17	100 / 100	320 ms	89292 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 (cur.f != mn[cur.s].s) {continue;}
		if (vis[cur.s]) {continue;}
		vis[cur.s] = true;


		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 mn[0].s << '\n';
	return ans;
}
/*
int main() {
	int n, m, k; cin >> n >> m >> k;
	int r[m][2],l[m],p[k];
	F0R(i,m) {cin >> r[i][0]>>r[i][1]>>l[i];}
	F0R(i,k) {cin >> p[i];}
	ll x = travel_plan(n,m,r,l,k,p);
	cout<<ans;
}*/

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