제출 #982060

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
982060		vjudge1	사이버랜드 (APIO23_cyberland)	C++17	0 / 100	36 ms	9348 KiB

cyberland

#include "cyberland.h"

#include <bits/stdc++.h>

#include <queue>
using namespace std;

using ll  = long long;
using pll = pair<ll, ll>;

double solve(int N, int M, int K, int H, std::vector<int> x,
             std::vector<int> y, std::vector<int> c,
             std::vector<int> arr) {
	vector<vector<pll>> G(N);
	vector<double>      dis(N);

	vector<bool> v(N);
	for (int i = 0; i < M; i++) {
		G[x[i]].push_back({y[i], c[i]});
		G[y[i]].push_back({x[i], c[i]});
	}
	if (N == 2 && !M) return -1;
	else if (N == 2)
		return c[0];

	priority_queue<pair<double, ll>, vector<pair<double, ll>>,
	               greater<pair<double, ll>>>
	  q;
	arr[0] = 0;

	{
		vector<bool> v(N);
		queue<ll>    qt;
		qt.push(0);
		while (qt.size()) {
			ll node = qt.front();
			qt.pop();
			if (v[node] || node == H) continue;
			v[node] = true;
			if (!arr[node]) q.push({0, node});
			for (pll& nei : G[node]) qt.push(nei.first);
		}
	}

	double ans = INT_MAX;
	while (q.size()) {
		ll     node = q.top().second;
		double c    = q.top().first;
		q.pop();
		if (node == H) ans = min(ans, c);
		if (v[node] || node == H) continue;
		v[node] = true;
		for (pll& nei : G[node]) q.push({nei.second + c, nei.first});
	}

	if (ans == INT_MAX) return -1;
	return ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3