글 읽기 - 다익스트라 DP관련 질문입니다

lifecream 2년 전 0

www.acmicpc.net/problem/16118

16118: 달빛 여우 문제에서와 같이

(v1, v2) edge 를 지났을 경우와 지나지 않았을 경우 두가지로 visited 2차원 배열을 구성했습니다.

1 -> v1 -> v2 -> N 이나

1 -> v2 -> v1 -> N 과 같이 다익스트라를 여러번 진행하는 것 이외에

아래 코드와 같이 DP를 사용하여 한번에 다익스트라를 진행하는 방법이 없을까요?

/*
백준 1504번
https://www.acmicpc.net/problem/1504
*/

//algorithm: Dijkstra

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#define MAX_SIZE 1001
#define INF 2000000000

using namespace std;

struct CMP {
	int node;
	int cost;
	int passed; //passed = 0 -> (v1,v2) edge x / passed = 1 -> (v1,v2) edge o
	bool operator()(CMP a, CMP b) {
		if (a.cost > b.cost) return true;
		else return false;
	}
};

int n, e, x;
int v1, v2;
vector<CMP> map[MAX_SIZE];
priority_queue<CMP, vector<CMP>, CMP> pq;
int dist[MAX_SIZE];
bool visited[MAX_SIZE][2]; //visited[][0] -> passed = false; visited[][1] -> passed = true;

void input(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> e;
	for (int i = 0; i < e; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		map[a].push_back({ b,c,0 });
		map[b].push_back({ a,c,0 });
	}
	cin >> v1 >> v2;
}

int Dijkstra(CMP start) {
	int ans = -1;
	pq.push(start);
	memset(visited, false, sizeof(visited));
	while (!pq.empty()) {
		CMP top = pq.top();
		pq.pop();
		if (visited[top.node][top.passed]) continue;
		if (top.passed == 1 && top.node == n) {
			ans = top.cost;
			break;
		}
		visited[top.node][top.passed] = true;
		for (int i = 0; i < map[top.node].size(); i++) {
			CMP arrival = map[top.node][i];
			if ((top.node == v1 && arrival.node == v2) || (top.node == v2 && arrival.node == v1) || top.passed == 1) arrival.passed = 1;
			if (visited[arrival.node][arrival.passed]) continue;
			pq.push({ arrival.node,arrival.cost + top.cost,arrival.passed });
		}
	}
	return ans;
}

int main(void) {
	input();
	cout << Dijkstra({ 1,0 });
	return 0;
}

qvixnh22 2년 전 0

map에 (v1,v2)간선이 없으면 다익스트라 우선순위 큐에 추가하는 조건이 약할 수 있습니다.

예)

5 4
1 2 10
2 3 10
3 4 10
4 5 10
2 4

위 예제의 경우 top.node==v1 && arrival.node==v2인 경우가 발생하지 않습니다. (역방향도 마찬가지입니다.) 따라서 -1을 출력하게 될겁니다. 실제 답은 4입니다.

v1, v2를 통과하지 않는 최단거리, v1만 통과하고 v2를 통과지 않는 최단거리, v2만 통과하고 v1을 통과하지 않는 최단거리, v1, v2를 모두 통과하는 최단거리를 구하는 방법이 있을텐데, 이 경우는 다익스트라를 여러 번 진행하는 것보다 느립니다.

lifecream 2년 전 0

네네 맞는거 같습니다 v1 v2를 지나야 한다는 말이 v1, v2를 연결하는 edge가 항상 존재한다는 뜻으로 잘못 이해했네요

말씀 듣고 조금 수정하여 풀어보았습니다 visited 배열의 두번째 인덱스를 4까지 늘려

Case 1: v1,v2 모두 방문 경우 (48번째 줄) -> visited[][3]

Case 2: v1 방문 경우 (49번째 줄) -> visited[][1]

Case 3: v2 방문 경우 (50번째 줄) -> visited[][2]

Case 4: v1,v2 모두 방문하지 않은 경우 (51번째 줄) -> visited[][0]

로 나누어 보았는데 이번에는 90% 가까이 올라갔다 틀렸습니다가 나오더라구요.

이번에도 질문에 있는 반례들은 모두 잘 작동합니다.

진짜 visited를 2차원 배열로 만들어 한번에 다익스트라를 진행하는 방법이 없을까요..?

/*
백준 1504번
https://www.acmicpc.net/problem/1504
*/

//algorithm: Dijkstra

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#define MAX_SIZE 1001
#define INF 2000000000

using namespace std;

struct CMP {
	int node;
	int cost;
	bool passed[2];
	bool operator()(CMP a, CMP b) {
		if (a.cost > b.cost) return true;
		else return false;
	}
};

int n, e;
int v1, v2;
vector<CMP> map[MAX_SIZE];
priority_queue<CMP, vector<CMP>, CMP> pq;
bool visited[MAX_SIZE][4]; //visited[][0] -> x / visited[][1] -> v1 / visited[][2] -> v2 / visited[][3] -> v1 & v2

void input(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> e;
	for (int i = 0; i < e; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		map[a].push_back({ b,c,0 });
		map[b].push_back({ a,c,0 });
	}
	cin >> v1 >> v2;
}

int set_index(bool* temp) {
	if (temp[0] && temp[1]) return 3;
	else if (temp[0]) return 1;
	else if (temp[1]) return 2;
	else return 0;
}

int Dijkstra(CMP start) {
	int ans = -1;
	pq.push(start);
	memset(visited, false, sizeof(visited));
	while (!pq.empty()) {
		CMP top = pq.top();
		pq.pop();
		int index = set_index(top.passed);
		if (index == 3 && top.node == n) {
			ans = top.cost;
			break;
		}
		if (visited[top.node][index]) continue;
		visited[top.node][index] = true;
		for (int i = 0; i < map[top.node].size(); i++) {
			CMP arrival = map[top.node][i];
			if (arrival.node == v1 || top.passed[0]) arrival.passed[0] = true;
			if (arrival.node == v2 || top.passed[1]) arrival.passed[1] = true;
			int arrival_index = set_index(arrival.passed);
			if (visited[arrival.node][arrival_index]) continue;
			pq.push({ arrival.node,arrival.cost + top.cost,{arrival.passed[0],arrival.passed[1]} });
		}
	}
	return ans;
}

int main(void) {
	input();
	cout << Dijkstra({ 1,0,{false,false} });
	return 0;
}

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

문제

문제

출처

ICPC

다익스트라 DP관련 질문입니다

lifecream 2년 전 0

qvixnh22 2년 전 0

lifecream 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말