글 읽기 - 1753번 두 코드의 차이가 무엇인가요? (정답 코드 포함)

doralife12 2년 전 0

두 코드 모두 예제 입력 1은 잘 작동합니다.

단순히 현재 위치와 cost의 위치를 바꾸었다는 것으로 이렇게 큰 차이가 발생할 수 있나요?

혹시 cost가 앞으로 오면서 cost가 낮은 것부터 체크해서 그런건가요?

// 맞았습니다가 나온 코드

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

using namespace std;

const int INF = 1000000000;

int V, E;
int start;
vector<pair<int, int>> graph[20001];
int cost[20001];

void dijkstra() {
	priority_queue<pair<int, int>> pQ;
	pQ.push({ 0, start });
	cost[start] = 0;

	while (!pQ.empty()) {
		int cCost = -pQ.top().first;
		int cur = pQ.top().second;
		pQ.pop();

		if (cCost > cost[cur]) continue;
		for (unsigned int i = 0; i < graph[cur].size(); i++) {
			int next = graph[cur][i].first;
			int distance = cCost + graph[cur][i].second;
			if (distance < cost[next]) {
				cost[next] = distance;
				pQ.push({ -distance, next });
			}
		}
	}
}

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

	cin >> V >> E;
	cin >> start;

	int u, v, w;
	for (int i = 0; i < E; i++) {
		cin >> u >> v >> w;
		graph[u].push_back({ v, w });
	}
	for (int i = 1; i <= V; i++)
		cost[i] = INF;

	dijkstra();

	for (int i = 1; i <= V; i++) {
		if (cost[i] == INF) cout << "INF" << '\n';
		else cout << cost[i] << '\n';
	}

	return 0;
}

// 시간 초과가 발생하는 코드
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int INF = 1000000000;

int V, E;
int start;
vector<pair<int, int>> graph[20001];
int cost[20001];

void dijkstra() {
	priority_queue<pair<int, int>> pQ;
	pQ.push({ start, 0 });
	cost[start] = 0;

	while (!pQ.empty()) {
		int cur = pQ.top().first;
		int cCost = -pQ.top().second;
		pQ.pop();

		if (cCost > cost[cur]) continue;
		for (unsigned int i = 0; i < graph[cur].size(); i++) {
			int next = graph[cur][i].first;
			int distance = cCost + graph[cur][i].second;
			if (distance < cost[next]) {
				cost[next] = distance;
				pQ.push({ next, -distance });
			}
		}
	}
}

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

	cin >> V >> E;
	cin >> start;

	int u, v, w;
	for (int i = 0; i < E; i++) {
		cin >> u >> v >> w;
		graph[u].push_back({ v, w });
	}
	for (int i = 1; i <= V; i++)
		cost[i] = INF;

	dijkstra();

	for (int i = 1; i <= V; i++) {
		if (cost[i] == INF) cout << "INF" << '\n';
		else cout << cost[i] << '\n';
	}

	return 0;
}

djm03178 2년 전 1

https://www.acmicpc.net/board/... 의 5번을 참고하세요.

doralife12 2년 전 0

아하 자세한 설명 감사합니다!

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

문제

문제

출처

ICPC

1753번 두 코드의 차이가 무엇인가요? (정답 코드 포함)

doralife12 2년 전 0

djm03178 2년 전 1

doralife12 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말