글 읽기 - 반례 부탁드립니다

ckdgus2482 2년 전 0

제가 지문을 잘못 이해한건지 틀렸다고 나오네요

코드를 간략히 설명드리자면

시작 위치에서 집까지 추적할 수 있도록 다익스트라 돌리면서 parent 배열을 구축합니다. 탐색 중에 기존에 발견한 최단 경로와 같은 길이의 경로를 발견했을 때 parent 값이 더 큰 것으로 갱신되도록 하여 지문에서 요구하는 최단경로를 찾습니다.

각 쿼리에 대해 순차적으로 구해둔 경로를 따라 가장 처음 만나는 재고가 있는 편의점을 찾습니다. 이 과정에서 경로압축을 수행하여 이후의 쿼리를 대비합니다.

제가 어떤 케이스를 놓친건가요?

#include<iostream>
#include<vector>
#include<queue>

using namespace std;
constexpr int INF = 987654321;
int N, M, K;
vector<int> A, dist, parent;
vector<vector<pair<int,int>>> adj;

int getFirstCon(int num)
{
	if (A[num]) return num;
	return parent[num] = getFirstCon(parent[num]);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> N >> M >> K;
	A.resize(N + 1);
	adj.resize(N + 1);
	dist.resize(N + 1, INF);
	parent.resize(N + 1, -1);
	for (int i = 1; i <= N; ++i)
		cin >> A[i];
	for (int i = 0; i < M; ++i)
	{
		int u, v, c;
		cin >> u >> v >> c;
		adj[u].emplace_back(v, c);
		adj[v].emplace_back(u, c);
	}

	priority_queue<pair<int, int>> pq; //<-cost, node>
	dist[1] = 0;
	parent[1] = 0;
	pq.emplace(0, 1);
	while (!pq.empty())
	{
		int curCost = -pq.top().first;
		int curNode = pq.top().second;
		pq.pop();
		if (dist[curNode] < curCost) continue;
		for (auto& next : adj[curNode])
		{
			int nextCost = curCost + next.second;
			if (nextCost < dist[next.first])
			{
				dist[next.first] = nextCost;
				parent[next.first] = curNode;
				pq.emplace(-nextCost, next.first);
			}
			else if (nextCost == dist[next.first] && parent[next.first] < curNode)
			{
				parent[next.first] = curNode;
			}
		}
	}

	A[0] = 1;
	for (int i = 0; i < K; ++i)
	{
		int s, sel = -1;
		cin >> s;
		if (parent[s] != -1)
		{
			sel = getFirstCon(s);
			if (sel == 0) //경로상의 편의점들 모두 재고 없음
				sel = -1;
			else
				--A[sel];
		}
		cout << sel << '\n';
	}
}

wnsduds1 2년 전 0

100만 * 1000 =10억 까지 나올 수 있어서 INF 값이 조금 더 커야할 것 같아요

ckdgus2482 2년 전 0

감사합니다 C 상한이 별로 안커서 무심코 넘어갔는데 계산해보니 그러네요 ㅜㅜ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례 부탁드립니다

ckdgus2482 2년 전 0

wnsduds1 2년 전 0

ckdgus2482 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말