글 읽기 - 1753번 cost에 -를 붙이는 이유가 뭔가요?

je1000413 5년 전 1

아래는 통과된 소스입니다.

31번째 줄에 cost 값에 -를 붙여서 넣으면 시간초과 문제가 해결되었습니다.

그런데 그 이유가 뭘까요...? ㅠㅠㅠㅠ

안 붙이면 시간초과가 납니다 ㅠㅠ

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

using namespace std;

long long dist[20001];
const int INF = 987654321;
vector<pair<int, int>> adj[20001];
priority_queue<pair<int, int>> pq; // 만약 앞에 값이 같다면, 뒤에 값에 따라 우선순위 결정
// 우선순위 큐는 들어간대로 나오는 것이 아니라, 우선순위가 높을 수록 먼저 나옴


int main() {

	int v, e, start;
	int x, y, add;

	cin >> v >> e >> start; // 점, 선, 시작점 받기

	while (e--) {
		cin >> x >> y >> add; // 출발점, 도착점 , 가중치
		adj[x].push_back(make_pair(y, add)); // 출발점.(도착점, 가중치) 벡터에 넣기
	}

	for (int i = 1; i <= v; i++) dist[i] = INF; // 1~ v까지 적당히 큰 값 넣기
	dist[start] = 0; // 자기 자신은 거리 0
	pq.push(make_pair(0, start)); // 시작점의 (걸리는 거리, 현재위치) 넣기

	while (!pq.empty()) {
		int cost = -pq.top().first; // 걸리는 비용 // "-" 안 넣었을 때는 시간초과.. 왜지?
		int point = pq.top().second; // 현재 시작점
		pq.pop(); // 날리고

		//다른점에서 돌았던 경우에 이미 그 자리에 값이 있을 수 있음
		if (cost > dist[point]) continue; // 비용이 더 크면 할 필요 없고
		
		for (int i = 0; i < adj[point].size(); i++) // vector는 0 자리부터 차례대로 들어가니까
		{
			int next = adj[point][i].first; // (1,"2",2), (1,"3",3)  
			int ncost = cost + adj[point][i].second; //(1,2,"2"), (1,3,"3")
			if (dist[next] > ncost) { 
				dist[next] = ncost;
				pq.push(make_pair(-ncost, next)); // 계산해줄 값 넣기
			}
		}
	}

	//출력
	for (int i = 1; i <= v; i++) {
		if (dist[i] == INF) cout << "INF" << '\n';
		else cout << dist[i] << '\n';

	}
}

jung2381187 5년 전 1

다익스트라 알고리즘은 값이 작은 거 부터 뽑아야 하는데, 그냥 priority_queue는 값이 큰 거 부터 뽑습니다. 그래서 마이너스를 붙인 다음 넣어주면 제대로 작동하죠

je1000413 5년 전 0

jung2381187 감사합니다!!

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

문제

문제

출처

ICPC

1753번 cost에 -를 붙이는 이유가 뭔가요?

je1000413 5년 전 1

jung2381187 5년 전 1

je1000413 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말