제출 #443841

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
443841		IvanJ	악어의 지하 도시 (IOI11_crocodile)	C++17	0 / 100	2088 ms	2636 KiB

crocodile

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

#define pb push_back
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e5 + 5;
const ll inf = 1e18;

int n, m, k;
vector<pair<int, ll>> adj[maxn];
int E[maxn];
pair<ll, ll> dist[maxn];

int solve() {
	set<pair<pair<ll, ll>, int>> s;
	for(int i = 0;i < n;i++) dist[i] = {inf, inf}, s.insert({dist[i], i});
	for(int i = 0;i < n;i++) {
		if(!E[i]) continue;
		dist[i] = {0, 0};
		s.erase({{inf, inf}, i});
		s.insert({dist[i], i});
	}
	
	for(int i = 0;i < n;i++) {
		//for(auto p : s) cout << "(" << p.y << " | " << p.x.x << " " << p.x.y << ")\n";
		pair<pair<ll, ll>, int> state = *s.begin();s.erase(s.begin());
		int x = state.y;
		pair<ll, ll> d = state.x;
		//cout << x << " -> " << d.x << ' ' << d.y << "\n";
		//cout << "\n";
		for(pair<int, ll> p : adj[x]) {
			if(s.find({dist[p.x], p.x}) != s.end())
				s.erase({dist[p.x], p.x});
			pair<ll, ll> di = dist[p.x];
			if(d.y + p.y < dist[p.x].y) {
				dist[p.x].x = dist[p.x].y;
				dist[p.x].y = d.y + p.y;
			} else if(d.x + p.y < dist[p.x].x) {
				dist[p.x].x = d.x + p.y;
			}
			if(di != dist[p.x]) s.insert({dist[p.x], p.x});
		}
	}

	return (int)dist[0].x;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  n = N, m = M, k = K;
  for(int i = 0;i < m;i++) {
	  adj[R[i][0]].pb({R[i][1], L[i]});
	  adj[R[i][1]].pb({R[i][0], L[i]});
  }
  for(int i = 0;i < k;i++) E[P[i]] = 1;
  
  return solve();
}

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