글 읽기 - KOI 다익스트라 질문입니다!

jangzzang 4년 전 0

도저히 방법이 안떠올라서 인터넷에서 해법을 보고 풀었습니다.

dp테이블을

dp[노드][현재까지오는 최소 기름값] = 비용 으로 잡고 다익스트라를 돌렸는데 제가 의문이 드는 부분은

51번째 줄의

if (node == n) {
ans = cost;
break;
}

부분입니다. 가장 먼저 dp[node][] 배열이 갱신되는 값이 최소의 비용이 보장 된다는게 잘 이해가 되지 않습니다.

ㅠㅠ 혹시 도움 주실 분 있으실까요?

#include<iostream>
#include<vector>
#include<queue>
#include<string.h>

using namespace std;
typedef long long ll;
typedef struct {
	ll cost;
	int node;
	ll price;
}info;
bool operator<(info A, info B) {
	return A.cost < B.cost;
}
typedef struct {
	int to;
	ll price;
}V;
ll dp[2550][2550];  // dp[노드][현재까지오는 최소 기름값] = 비용
ll oil[2550];
priority_queue<info> pq;
vector<V> vt[2550];
int n, m;
int main() {

	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)scanf("%lld", &oil[i]);
	for (int i = 1; i <= m; i++) {
		int x; int y; ll p;
		scanf("%d %d %lld", &x, &y, &p);
		vt[x].push_back({ y,p });
		vt[y].push_back({ x,p });
	}
	memset(dp, -1, sizeof(dp));
	ll ans = 21000000000000;
	pq.push({ 0,1,oil[1] });
	while (!pq.empty()) {
		ll cost;
		int node;
		ll price;
		do {
			cost = -pq.top().cost;  // 현재까지 들고온 비용
			node = pq.top().node;
			price = pq.top().price; // 현재까지 가지고 온 최소 기름값.
			pq.pop();
		} while (!pq.empty() && dp[node][price] != -1);

		if (dp[node][price] != -1)break;
		dp[node][price] = cost;
		if (node == n) {
			ans = cost;
			break;
		}

		for (int i = 0; i < vt[node].size(); i++) {
			int nxt = vt[node][i].to;
			ll plus = cost + min(oil[node], price) * vt[node][i].price;
			if (dp[nxt][min(oil[node],price)] != -1)continue;
			pq.push({ -plus,nxt,min(oil[node],price) });
		}
	}
	printf("%lld", ans);
}

sait2000 4년 전 2

다익스트라는 출발점에서부터의 거리가 가까운 정점 순서로 방문하기 때문에 그렇습니다. 즉, 한번 도착점에 방문하게 되면 그 다음에 확인할 때는 무조건 더 먼 거리로 방문한 경우에 해당됩니다.

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

문제

문제

출처

ICPC

KOI 다익스트라 질문입니다!

jangzzang 4년 전 0

sait2000 4년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말