글 읽기 - 30%에서 런타임에러가 뜨네요

joy144 4년 전 0

제출하면 30%에서 런타임에러가뜨고

6 9
1
1 2 10
1 3 30
1 4 15
2 5 20
3 6 5
4 3 5
4 6 20
6 4 20
5 6 20

로 테스트 해보면 vector iterator incompatible가 뜨네요

어디서 오류가 나는지 알만하신분 계신가요?

중요한진 모르겠지만, 예제는 되네요......

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <iterator>

using namespace std;

#define Edge pair<int, int>
#define PAIR pair<int, int>
#define DT first		//destination
#define WT second		//weight
#define INF 3000000		//최대거리보다 큰 값, 무한대와 비슷하게 사용

struct cmp {
	bool operator()(Edge &a, Edge &b) {
		return a.second > b.second;
	}
};

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);





	int V, E;
	cin >> V >> E;

	vector<int> dist(V + 1);		//아래블럭은 dist를 시작위치말고 싹 INF로고정해준다
	int start = 0;
	cin >> start;
	for (int i = 1; i <= V; i++)
		dist[i] = INF;
	dist[start] = 0;

	vector<vector<Edge>> edge(V + 1); //edge[u]에 목적지가v이고 가중치가 e인 pair를 넣는다
	int u, v, e;
	for (int i = 1; i <= E; i++) {
		cin >> u >> v >> e;
		edge[u].push_back(Edge(v, e));
	}

	/*for (int i = 1; i <= V; i++) {
		cout << "Line " << i << " : " << endl;
		for (auto it = edge[i].begin(); it != edge[i].end(); it++) {
			cout << it->DF << ' ' << it->WT << endl;
		}
	}*/

	vector<int> visit(V + 1);
	priority_queue<PAIR, vector<PAIR>, cmp> Q;//top이 현재의 위치, 시작점과의 거리를 가지도록하는 우선순위큐

	//visit[start] = 1;
	Q.push(Edge(start, dist[start]));





	while (!Q.empty()) {

		int accomDist = dist[Q.top().first];	//누적된거리

		for (auto it = edge[Q.top().first].begin(); it != edge[Q.top().first].end(); it++) {
			if ((it->WT + accomDist) < dist[it->DT]) { //거리갱신용
				dist[it->DT] = (it->WT + accomDist);
			}   
			Q.push(*it);
		}
		
		visit[Q.top().first] = 1;
		Q.pop();
	
	}






	for (int i = 1; i <= dist.size() - 1; i++) {
		if (dist[i] != INF)
			cout << dist[i] << endl;
		else
			cout << "INF" << endl;
	}
	cout << endl;

	return 0;
}

pichulia 4년 전 1

73번째 줄에 push한 값으로 인해서 top().first 가 달라져버리면

auto it 가 있는 for문은 언제 끝나게 될까요....

int cur_i = Q.top().first;

이런식으로 어딘가 변수를 사용해서 값을 꺼내놓은 다음에

바로 pop을 해야지 정상적으로 동작할듯 합니다.

joy144 4년 전 0

우선순위큐의 top()이 계속변하는군요!

pichulia님댓글과 질문게시판을 참조해서 짜서 성공했습니다!

답변감사드려요!

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

문제

문제

출처

ICPC

30%에서 런타임에러가 뜨네요

joy144 4년 전 0

pichulia 4년 전 1

joy144 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말