글 읽기 - c++ 5%에서 시간 초과좀 봐주세요

sanha93 5년 전 0

맨 처음 인접 리스트로 받아서

스타트 지점에서 거리백터 하나 만들고

중복으로 대기 순위에 쌓이는걸 방지하기 위해서

set에 해야 할 것들을 넣어두고

set내용이 하나도 없을때까지 진행하였는데

왜 시간 초과가 나는것일까요?

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
#include <set>

#define INF 400000
using namespace std;

void daik(vector<vector<pair<int, int>>> line, int sp, int N) {

	int j;
	vector<int> D(N + 1, INF);
	set<int> s;

	int cp = 1;
	for (int i = 0; i < line[sp].size(); i++) {
		D[line[sp][i].first] =(line[sp][i].second);
		s.insert(line[sp][i].first);
	}
	D[sp] = 0;
	set<int>::iterator iter;
	iter = s.begin();
	while (s.size()) 
	{
		if (iter == s.end())
			iter = s.begin();
		j = *iter;
		for (int i = 0; i < line[j].size(); i++) {
			if (line[j][i].second + D[j]< D[line[j][i].first]) {
				D[line[j][i].first] = (line[j][i].second + D[j]);
				s.insert(line[j][i].first);
				cp++;
			}
		}
		++iter;
		s.erase(j);
		
	}

	for (int i = 1; i < N+1; i++) {
		if (D[i] == INF)
			cout << "INF\n" ;
		else
			cout <<D[i]<< "\n";
	}
}
int main() {
    
    ios_base::sync_with_stdio(false);
    cin.tie(0); 
    
	int N, M, startPoint;
	int tmpStart, tmpEnd, tmpWeight;

	cin >> N >> M >> startPoint;
	vector<vector<pair<int, int>>> line(N + 1);

	for (int i = 0; i < M; i++) {
		cin >> tmpStart >> tmpEnd >> tmpWeight;
		line[tmpStart].push_back(make_pair(tmpEnd, tmpWeight));
	}
	daik(line, startPoint, N);
	return 0; 
}

djm03178 5년 전 0

set에 원소를 삽입하거나 삭제를 했다면 그 때까지 만들어진 모든 iterator는 무효화가 됩니다. 그대로 사용을 해서는 안 됩니다.

그리고 어떤 시점의 begin에서 시작한 것 이후로 쭉 진행하면서 뽑아오는 것이 아니라, 매번 가장 가까운 거리의 정점을 뽑아와야 합니다. 즉, 매 루프마다 begin()을 불러와야 합니다.

sanha93 5년 전 0

아 가장 가까운 거리 정점부터 탐색 해야 하는거군요

iterator 는 문제 없이 처리 됬었습니다.

다음 걸로 iteraator 옮겨 놓고 그전꺼 삭제하면 문제 없더라구요

djm03178 5년 전 0

아 그러네요. 찾아보니 지워진 iterator만 무효화되는군요.

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

문제

문제

출처

ICPC

c++ 5%에서 시간 초과좀 봐주세요

sanha93 5년 전 0

djm03178 5년 전 0

sanha93 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말