글 읽기 - 다익스트라로 풀었는데 질문 있습니다.

sweeetcody 4년 전 0

아래 코드처럼 큐에 음수로 넣어서 순위가 높게 지정하는 경우에는 실패고, greater로 시간이 낮은게 순위가 높게 되도록 하면 답이 맞습니다.

제가 잘못이해하고 사용하고 있는 것 인가요?

#include<cstdio>
#include<queue>
#include<vector>
#include<functional>
using namespace std;

int map[100001];
bool visited[100001];
int main()
{
	int n, k;
	scanf("%d %d", &n, &k);
	priority_queue<pair<int, int>, vector<pair<int, int> > > pq;
	//priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int > > > pq;

	pq.push({0, n });
	visited[n] = true;
	while (!pq.empty())
	{
		int now = pq.top().second;
		int cnt = -pq.top().first;
		pq.pop();
		if(now == k)
		{
			printf("%d", cnt);
			return 0;
		}
		if (now * 2 <= 100000 && !visited[now * 2])
		{
			pq.push({ -(cnt),now*2 });
			visited[now * 2] = true;
		}
		if (now + 1 <= 100000 && !visited[now + 1])
		{
			pq.push({ -(cnt + 1),now + 1 });
			visited[now + 1] = true;
		}
		if (now - 1 >= 0 && !visited[now - 1])
		{
			pq.push({ -(cnt + 1),now - 1 });
			visited[now - 1] = true;
		}


	}
}

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

문제

문제

출처

ICPC

다익스트라로 풀었는데 질문 있습니다.

sweeetcody 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말