글 읽기 - C++ 다익스트라 시간초과...

fdsajklt2 4년 전 0

플로이드 와샬을 공부하기전인데요..

가중치가 자연수여서 다익스트라를 사용하면 풀리겠다 싶어서 풀었는데 시간초과가 떠서 질문드립니다..

혹시 제가 다익스트라를 잘못 구현한것인지 아니면 애초에 다익스트라로 풀면 안되는 문제인지 궁금하여 질문드립니다!

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<cmath>
#include<stack>

using namespace std;

#define INF 1600000001

int V, E;
int arr[401][401];

vector<vector<pair<int, int>>> v(401);		//도착점, 가중치 
priority_queue<pair<int, int>> pq;			//가중치 합산, 도착점

void Dijkstra(int start) {

	while (!pq.empty()) {
		int next = pq.top().second;
		int sum = -1 * pq.top().first;
		pq.pop();
		if (arr[start][next] > sum) {		//최단 경로 업데이트시 
			arr[start][next] = sum;

			for (int i = 0; i < v[next].size(); i++) {
				int newnext = v[next][i].first;
				int weight = v[next][i].second;
				pq.push({ -1 * (weight + sum) , newnext });
			}

		}
	}
}
int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> V >> E;

	int src, dest, weight;
	for (int e = 0; e < E; e++) {
		cin >> src >> dest >> weight;
		v[src].push_back({ dest,weight });
	}

	//arr초기화
	for (int x = 1; x < 401; x++) {
		for (int y = 1; y < 401; y++) {
			arr[x][y] = INF;
		}
	}

	//각 정점마다 다익스트라 실행
	for (int i = 1; i <= V; i++) {
		int now = i;

		for (int j = 0; j < v[i].size(); j++) {
			int next = v[i][j].first;
			int weight = v[i][j].second;
			pq.push({ weight * -1 , next });
		}
		Dijkstra(now);
	}


	//사이클을 이룰때 최단거리 찾기
	int answer = INF;
	for (int i = 1; i <= V; i++) {
		if (arr[i][i] < answer) answer = arr[i][i];
	}
	cout << answer << "\n";
}

chw0501 4년 전 1

일단은 플로이드로 푸는 것이 시간복잡도 상으로는 더 좋습니다. O(n^3)

하지만 각 정점마다의 다익스트라로도 풀 수 있습니다. O(V* ElogV)

위 코드에서 몇가지 잘못된 부분이 있습니다.

다익스트라의 구현 방식을 다시 보면 좋으실 거 같은데,

1. 25번 째 줄에서 if (arr[start][next] >= sum) 로 수정되어야 합니다. sum과 같을 때에도 그 경로에 대해서는 업데이트를 해줘야 되기 때문입니다.

2. 사실 이것때문에 시간초과가 난 것인데 28 ~ 32번째 줄에서 아래 코드와 같이 수정되어야 합니다. 더 짧은 경로를 발견했을 때만 arr을 갱신해주고 우선순위 큐에 저장을 해야 우선순위 큐에 저장되는 간선 개수가 E개를 넘지 않을 것이기 때문입니다.

마지막으로

3. answer ==INF 일때는 -1을 출력해야 합니다.

for (int i = 0; i < v[next].size(); i++) {
    int newnext = v[next][i].first;
    int weight = v[next][i].second;
    if(arr[start][newnext]>arr[start][next]+weight){
        arr[start][newnext]=arr[start][next]+weight;   
        pq.push({ -1 * (weight + sum) , newnext });
    }
}

fdsajklt2 4년 전 0

원래 코드가 개판이었는데... 잘 알아보시고 도움주셔서 감사합니다!!!

혹시 1번. sum이 같을때에도 포함되야한다고 하셨는데, 제 생각에는 어차피 같다면 해당 목적지까지의 거리는 변하지 않기때문에

굳이 if문안에 들어가서 해당 목적지에서의 간선들을 봐봤자 그 전에 최단경로가 update되었을때 봤기때문에 중복된 과정이라고 생각되는데...

반례가 있을까요..?

chw0501 4년 전 0

sum과 같을 때 해당 목적지까지의 거리는 변하지 않지만, 그 목적지로부터 새롭게 update를 해야되기 때문에 포함되어야 합니다.

그 목적지로부터 update하는 과정은 그 전에 없었습니다.

fdsajklt2 4년 전 1

이제야 이해했네요! 정말 감사합니다~

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

문제

문제

출처

ICPC

C++ 다익스트라 시간초과...

fdsajklt2 4년 전 0

chw0501 4년 전 1

fdsajklt2 4년 전 0

chw0501 4년 전 0

fdsajklt2 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말