글 읽기 - [급(군인)] 9%에서 런타임에러,,,

37sadan_tongsinbyung 3년 전 0

싸지방 컴퓨터가 느려서 제대로 확인은 안되는데 9%에서 런타임 에러가 뜨는 것 같습니다 ㅜㅜ

질문에 검색해봤을 때 나오는 예제들도 넣어봤는데 잘 돌아가는 것 같습니다...

https://www.acmicpc.net/problem/1916 이 문제도 이 코드를 수정해서 제출해보니 맞았구여..

왜 런타임 에러가 뜰까요...? 군대 안이라 시간이 없어 도움이 절실합니다 ㅜㅜ

#include <stdio.h>
#include <queue>
#include <utility>
#include <vector>
#define PII pair<int,int>
#define NODE first
#define COST second
#define INF 2147483647
using namespace std;
int main() {
	int v, e, s, from, to, l;
	scanf("%d %d %d", &v, &e, &s); //노드, 간선, 시작점
    vector<vector<PII>> graph(v+1, vector<PII>()); //노드간 거리 인접행렬, <to,length>
	vector<int> dist(v+1, INF); //index 노드까지의 최단 거리
	while(e--) { //간선 입력
		scanf("%d %d %d", &from, &to, &l);
		graph[from].push_back(make_pair(to,l));
	}
	priority_queue<PII> pq; //우선순위 큐 선언
	pq.push(make_pair(s, dist[s] = 0)); //시작지점 거리 0 초기화 동시에 우선순위 큐에 시작점 삽입
	while(!pq.empty()) { //다익스트라
		int now_node = pq.top().NODE, now_cost = pq.top().COST;
		pq.pop();
		if(dist[now_node] < now_cost) continue; //긴 거리 컷
		for(int i = 0; i < graph[now_node].size(); i++) { //현재 노드를 경유하는 거리가 최단이면 갱신
			int next_node = graph[now_node][i].NODE;
			int next_cost = graph[now_node][i].COST;
			if(dist[next_node] > now_cost + next_cost) {
				dist[next_node] = now_cost + next_cost;
				pq.push(make_pair(next_node, dist[next_node])); //다음 점 삽입
			}
		}
	}
	for(int i = 1; i <= v; i++) { //각 노드까지의 최단거리 출력
		if(dist[i] == INF) printf("INF\n");
		else printf("%d\n", dist[i]);
	} 
	return 0;
}

pinebananais 3년 전 1

1. priority_queue 컨테이너는 기본적으로 큰 값을 우선 순위가 높은 값이라고 판정합니다. 따라서 min heap으로 만들어 줄 필요가 있습니다.
-> priority_queue<PII> 를 priority_queue<PII, vector<PII>, greater<PII>> 로 수정해 주시면 됩니다.

2. pair 객체의 순서는 앞의 값에 의해 결정 (같은 경우에만 뒤의 값에 의해 결정) 됩니다. 따라서 cost를 기준으로 heap을 만드려면 pair의 첫 번째 값에 cost를 넣어 주어야 합니다.

-> pair를 만들고 넣을 때 node, cost 순서가 아닌 cost, node 순서로 만들어야 합니다.

위의 두 개를 고치면 AC를 받습니다.

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

문제

문제

출처

ICPC

[급(군인)] 9%에서 런타임에러,,,

37sadan_tongsinbyung 3년 전 0

pinebananais 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말