제출 #109144

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
109144		pamaj	악어의 지하 도시 (IOI11_crocodile)	C++14	100 / 100	845 ms	63496 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;

typedef pair<int, int> pii;

int vis[maxn], dist[maxn], dist2[maxn];
vector<pii> G[maxn];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	memset(dist, 0x3f3f3f3f, sizeof(dist));
	memset(dist2, 0x3f3f3f3f, sizeof(dist));

	for(int i = 0; i < M; i++)
	{
		int a = R[i][0], b = R[i][1];

		G[a].push_back({L[i], b});
		G[b].push_back({L[i], a});
	}

	// for(int i = 0; i < N; i++)
	// 	for(auto u : G[i])
	// 		cout << i << " " << u.second << " " << u.first << "\n";

	priority_queue<pii, vector<pii>, greater<pii>> q;

	for(int i = 0; i < K; i++)
	{
		dist[P[i]] = dist2[P[i]] = 0;
		q.push({0, P[i]});
	}

	while(!q.empty())
	{
		auto a = q.top();
		q.pop();

		//cout << a.second << " \n";

		if(vis[a.second]) continue;
		vis[a.second] = true;

		for(auto u : G[a.second])
		{
			if(dist[u.second] > dist2[a.second] + u.first)
			{
				dist2[u.second] = dist[u.second];
				dist[u.second] = dist2[a.second] + u.first;

				// CÓDIGO MÁGICO COMEÇA AQUI
				if (dist2[u.second] != dist[u.second])
					q.push({dist2[u.second], u.second});
				// CÓDIGO MÁGICO TERMINA AQUI
			}
			else if(dist2[u.second] > dist2[a.second] + u.first)
			{
				dist2[u.second] = dist2[a.second] + u.first;
				q.push({dist2[u.second], u.second});
			}

		}
	}

	return dist2[0];
}

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