글 읽기 - 반례를 찾아주실 고수님!

shdlehdwls 5년 전 0

다익스트라로 시도했는데, 계속 오답뜹니다,,,ㅠㅠ

질문에 올라와 있는 테스트케이스도 다 만족하는데, 어떤 반례가 있는지 모르겠네요,,ㅠ

고수님들 부탁드립니다.,ㅠ

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define INF -1

using namespace std;

typedef struct Edge
{
	int to;
	int weight;
}Edge;

typedef struct Comp
{
	bool operator() (Edge edge1, Edge edge2)
	{
		return edge1.weight > edge2.weight;
	}
}Comp;

int main()
{
	int N, K;
	cin >> N >> K;

	priority_queue<Edge, vector<Edge>, Comp>pq;
	vector<int> distance(100000, INF);
	vector<int> path(100000, INF);

	Edge start;
	start.to = N;
	start.weight = 0;
	pq.push(start);
	distance[N] = 0;
	path[N] = 0;

	while (!pq.empty())
	{
		Edge here = pq.top(); pq.pop();
		int pre = here.to - 1;
		int post = here.to + 1;
		int teleport = here.to * 2;

		if (pre >= 0)
		{
			int min_distance = distance[here.to] + 1;
			if (distance[pre] == INF)
			{
				distance[pre] = min_distance;
				path[pre] = here.to;
				Edge next;
				next.to = pre;
				next.weight = 1;
				pq.push(next);
			}
			if (distance[pre] > min_distance)
			{
				distance[pre] = min_distance;
				path[pre] = here.to;
			}
		}
		if (post < 100000)
		{
			int min_distance = distance[here.to] + 1;
			if (distance[post] == INF)
			{
				distance[post] = min_distance;
				path[post] = here.to;
				Edge next;
				next.to = post;
				next.weight = 1;
				pq.push(next);
			}
			if (distance[post] > min_distance)
			{
				distance[post] = min_distance;
				path[post] = here.to;
			}
		}
		if (teleport < 100000)
		{
			int min_distance = distance[here.to];
			if (distance[teleport] == INF)
			{
				distance[teleport] = min_distance;
				path[teleport] = here.to;
				Edge next;
				next.to = teleport;
				next.weight = 0;
				pq.push(next);
			}
			if (distance[teleport] > min_distance)
			{
				distance[teleport] = min_distance;
				path[teleport] = here.to;
			}
		}
	}
	/*
	for (int u = 0; u < 100000; u++)
	{
		cout << distance[u] << " ";
	}
	cout << endl;
	*/
	cout << distance[K] << endl;
	return 0;
}

shdlehdwls 5년 전 0

해결했습니다!

다익스트라에서 방문하지 않은 노드뿐만 아니라, 갱신되어야 하는 노드들도 힙에 저장을 했어야했네요,,

아직도 공부가 부족한걸 느낍니다,,ㅠ

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

문제

문제

출처

ICPC

반례를 찾아주실 고수님!

shdlehdwls 5년 전 0

shdlehdwls 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말