oj.uz

답안 #109143

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
109143 2019-05-04T17:39:07 Z pamaj 악어의 지하 도시 (IOI11_crocodile) C++14
0 / 100
 5 ms 3456 KB 
#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
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 3456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 3456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 3456 KB Output isn't correct
2 Halted 0 ms 0 KB -