글 읽기 - 거의최단경로 c++ 시간초과입니다.

minhye11 4년 전 0

다익스트라 -> dfs(?) -> 다익스트라 순서대로 구현한거구요.

왜 시간초과가 나는지 잘 모르겠습니다.

질문 리스트에는 시간초과에 대한 이야기가 없어서 문제점을 찾기가 어렵습니다ㅜ

도움주시면 감사하겠습니다!

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int N, M;

vector <pair<int, int> > v[500]; // 간선정보
vector <int> dfs_v;
int d[500]; // 최소비용
int no_visit[500][500];
int number;
int INF = 1000000000;
int min_Dist;
int tot_Dist;
int start, end_;
bool is_searched[500];

void dijkstra(int start) {
	d[start] = 0;
	priority_queue <pair<int, int> > pq;
	pq.push({ 0, start });
	while (!pq.empty()) {
		int current = pq.top().second;
		int distance = -pq.top().first;
		pq.pop();
		if (d[current] < distance) continue;
		for (int i = 0; i < v[current].size(); i++) {
			int next = v[current][i].first;
			if (no_visit[current][next] == -1) continue;
			int nextDist = distance + v[current][i].second;
			if (nextDist < d[next]) {
				d[next] = nextDist;
				pq.push({ -nextDist, next });
			}
		}
	}
}

void dfs(int start) {
	if (start == end_) {
		if (tot_Dist == min_Dist) {
			for (int i = 0; i < dfs_v.size(); i++) {
				int a, b;
				if (i == dfs_v.size() - 1) {
					a = dfs_v[i];
					b = end_;
				}
				else {
					a = dfs_v[i];
					b = dfs_v[i + 1];
				}
				no_visit[a][b] = -1;
			}
		}
		return;
	}
	is_searched[start] = true;
	dfs_v.push_back(start);
	for (int i = 0; i < v[start].size(); i++) {
		int x = v[start][i].first;
		if (is_searched[x] == 0) {
			int tmp = v[start][i].second;
			tot_Dist += tmp;
			dfs(x);
			tot_Dist -= tmp;
		}
	}
	is_searched[start] = false;
	dfs_v.pop_back();
}

void initialize1() {
	for (int i = 0; i < number; i++) {
		d[i] = INF;
	}
	for (int i = 0; i < M; i++) v[i].clear();
	dfs_v.clear();
	memset(no_visit, 0, 500 * 500);
}

void initialize2() {
	for (int i = 0; i < number; i++) {
		d[i] = INF;
	}
}

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

	while (1) {
		cin >> N >> M;
		if (N == 0 && M == 0) break;
		number = N;
		cin >> start >> end_;
		initialize1();
		for (int i = 0; i < M; i++) {
			int a, b, c;
			cin >> a >> b >> c;
			v[a].push_back({ b, c });
		}
		dijkstra(start);
		min_Dist = d[end_];
		initialize2();
		tot_Dist = 0;
		dfs(start);
		dijkstra(start);
		if (d[end_] == INF) cout << "-1\n";
		else cout << d[end_] << "\n";
	}
}

seico75 4년 전 1

작성하신 코드는.

최단 거리를 찾고,

dfs 로 전체 경로를 다 가보면서 최단 경로일 경우 그 경로를 제외시키고

다시 최단 경로를 찾는 방법으로 보입니다.

두번째 전체 경로를 다 뒤지면서 경로를 제외하는 방법은 시간이 많이 걸립니다.

그래서 최단 경로를 찾을 때 최단 거리 갱신시 누구로 부터 갱신되었는지.. 그러니까 어디로부터 온 것이 최단 경로인지 기록하면 (parent) 빨리 지울 수 있습니다.

35라인 근처에 parent 를 저장/갱신하는 부분을 넣으면 됩니다.

다만, 모든 최단 경로를 다 고려해야 하므로 하나의 노드에 복수의 parent 가 있을 수 있다는 것을 고려해야합니다.

그리고..

78라인에 M 이 아니라 N일것 같습니다.

63라인에 0 이 아니라 false 가 바른 표현일 것 같습니다.

minhye11 4년 전 0

답변 정말 감사합니다!!! 35번째 줄에 parent를 어떻게 저장/갱신할지 모르겠어서..

지우는 함수를 따로 만들어서 경로를 역추적하며 없애주는 방식으로 진행하였습니다!!

seico75 4년 전 0

부모가 하나일 경우는

int parent[501];

를 만들어 두고 35 라인 근처에서

parent[next] = current;

이런 식으로 next 에 올때 어디서 오는 것이 최단인지를 저장하면되고..

end_ 부터 parent 를 따라가면서 start 까지 가면 최단 경로를 알 수 있습니다.

이 문제에서는 모든 최단 경로를 다 지워야 하므로

vector<int> parent[501];

으로 만들어야 하고, 35 라인 근처에서 parent[next].clear(); parent[next].push_back(current); 를 해야하고..

경로가 같을 경우는 push_back 만..

나중에 지울때는 dfs 로 해서 모든 parent 를 다 서치하면서 지우시면 됩니다.

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

문제

문제

출처

ICPC

거의최단경로 c++ 시간초과입니다.

minhye11 4년 전 0

seico75 4년 전 1

minhye11 4년 전 0

seico75 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말