글 읽기 - 1238 파티 제가 성공은 하였지만 더 좋은 방법이있나 싶어 질문드립니다.

skynet0149 6년 전 1

주석으로 질문부분이라고 표시해두었습니다. 참고해주시면 감사하겠습니다.

저의 생각은 각 정점별로 시작해서 X로 향한다음 X에서 각 정점으로 향하는 거리를 하나의 배열에 저장해야된다고 생각합니다.

이유는 dist 배열 같은 경우는 각정점별로 시작하는 최단거리를 알고있기 때문입니다.

이렇게 하니 시간이 224ms가 나오는데 조금 더 좋은 방법이 있는가 싶어 질문드립니다...

다른 분들의 코드를 보면 다익스트라 알고리즘을 2번만 돌리면 된다고 하시는데 그 코드를 봐도 잘 이해가 안되어 이렇게 질문드립니다. 제가 아직 코딩의 초보라 잘부탁드립니다.

#include <cstdio>
#include <queue>
#include <vector>
#include <climits>
using namespace std;
vector< pair<int, int> >adj[1001];
int N, M, X;
int dijkstra(int start, int end) {
	vector<int> dist(N + 1, INT_MAX);
	dist[start] = 0;
	priority_queue<pair<int, int>> pq;
	pq.push(make_pair(0, start));
	while (!pq.empty()) {
		int here = pq.top().second;
		int cost = -pq.top().first;
		pq.pop();

		int size = adj[here].size();
		for (int i = 0; i < size; i++) {
			int nthere = adj[here][i].first;
			int ncost = cost + adj[here][i].second;
			if (ncost < dist[nthere]) {
				dist[nthere] = ncost;
				pq.push(make_pair(-ncost, nthere));
			}
		}
	}
	return dist[end];
}
int main() {
	
	int u, v, w;
	scanf("%d %d %d", &N, &M, &X);
	
	for (int i = 0; i < M; i++) {
		scanf("%d %d %d", &u, &v, &w);
		adj[u].push_back(make_pair(v, w));
	}

	vector<int> save(N + 1, INT_MAX);
	for (int i = 1; i <= N; i++)                //질문 부분
		save[i] = dijkstra(i, X) + dijkstra(X, i);
	
	int max = save[1];
	for (int i = 2; i <= N; i++) {
		if (max < save[i])
			max = save[i];
	}

	printf("%d\n", max);

	return 0;
}

sgchoi5 6년 전 1

문제 화면에서 "맞은 사람" 선택하시고 공개된 코드를 보시면 됩니다. 더 빠른 수행시간을 가진..

skynet0149 6년 전 0

네 그렇게 해서 봤는데 이해가 잘안되서요... ㅠ 제가 질문 방법이 잘못되었는 것 같습니다. 감사합니다.

jh05013 6년 전 4

정점 x에서 모든 정점으로 가는 최단거리를 다익스트라로 구합니다.

모든 정점에서 x로 가는 최단거리를 구하려면 간선의 방향을 전부 뒤집은 다음 x에서 다익스트라 알고리즘을 돌리면 됩니다. "x에서 y로 가는 경로"의 간선의 방향을 뒤집으면 "y에서 x로 가는 경로"가 되기 때문입니다.

skynet0149 6년 전 1

x에서 모든정점으로 가는 최단거리까지는 이해를 하였습니다.

제가 여기서 간선의 방향을 전부 뒤집는다고 말씀을 하셨는데 이 문제는 단방향으로 알고있는데 뒤집어서 구해도 상관이 없는 건가요?

저는 간선 뒤집는 코드를 보았는데 간선을 뒤집어서 해도 왜 되는지 잘 이해가 안가더라구요...

그리고 항상 댓글 잘 달아주셔서 감사합니다.

djm03178 6년 전 2

y에서 x로 가는 경로라는 건, x에서 출발해 간선을 역으로 이용해서 y로 가는 경로랑 같습니다. y에서 x로 이동하는 과정을 영상으로 찍고, 그걸 역재생 한다고 생각해보세요. 그러면 모든 간선의 방향을 뒤집은 것처럼만 이동할 수 있습니다.

skynet0149 6년 전 1

djm03178님 답변 감사드립니다.

제가 궁금한것은 1이 시작점 3이 도착점이라 할 경우 1->2, 2->3, 3->1 이런식으로 연결되었다면 1->2->3->1 이런식으로 갈 수 도 있지않나요?

단방향이기 때문에 무조건 뒤집기만하면 연결이 되어있을 수도 있고 안되어 있을 수도 있기 때문에 저는 뒤집는 방법을 이해를 못하겠습니다...

제가 너무 초보라서 이해가 잘 안되는 것 같습니다.

djm03178 6년 전 4

지금 이 풀이는 저 과정을 둘로 쪼개서, 우선 1에서 3으로 가는 경로는 1->2, 2->3입니다. 여기까지가 1에서 3으로 다익스트라를 한 상태입니다.

여기서 경로를 다 뒤집습니다. 그러면 2->1, 3->2, 1->3이라는 경로가 만들어지죠. 그러고 다시 1에서부터 다익스트라를 합니다. 그러면 1->3 이라는 경로가 나오죠. 물론 이건 뒤집어진 경로이기 때문에, 실제로는 3->1인 경로입니다.

둘을 합치면 1->2->3->1 이라는 경로가 나옵니다. 그런데 다익스트라는 한 점에서 모든 점으로의 경로를 구하기 때문에, 이 과정에서 1에서 2로 가는 경로나, 2에서 1로 돌아오는 경로도 함께 구할 수 있습니다.

skynet0149 6년 전 2

아... 그러면 다익스트라를 x를 기준으로 한번 시작정점을 기준으로 다익스트라를 할 경우에는 그래프를 뒤집은 다음 다시 시작정점에서 x로 하면

된다는 말씀이시죠??

djm03178 6년 전 2

넵 그렇게 하면 됩니다.

skynet0149 6년 전 3

djm03178 님 친절한 답변 정말 감사합니다.

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