코드 복사/붙여넣기 하는 당신이 아름답습니다.

13308 : 주유소

풀이

2016 koi 전국대회 2번 문제이다.

뭔가 코드가 dp인 것 같기도 하고 아닌 것 같기도 한데 어쨌든 다익스트라+dp 그런 느낌으로 풀었다.

음 생각해보니 dp가 맞네 dp[i][j] = 노드i에서 기름값j로 놓고 풀면 된다!

여기서 트릭(?)을 한 번 써보자.

priority_queue에서 dst가 가장 작은 노드부터 꺼내기 때문에 dp[i][j] (== vst[i][j])에 방문했었다면

이미 지금보다 작은 값으로 방문했었음이 보장된다.

그래서 bfs 돌릴 때랑 똑같이 풀면 된다. visted면 방문하지 않아도 된다.

코드

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int n_ = 2500 + 10;

struct node {
	int idx, cst;
	ll dst;
	node(int idx, int cst, ll dst) : idx(idx), cst(cst), dst(dst) {}
	bool operator <(node A)const { return dst > A.dst; }
};

bool vst[n_][n_];
int n, m, cst[n_];
vector<pii> gph[n_];
priority_queue<node> pq;

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) scanf("%d", &cst[i]);
	for (int i = 0; i < m; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		gph[a].push_back({ b, c });
		gph[b].push_back({ a, c });
	}

	pq.push(node(1, cst[1], 0));
	while (!pq.empty()) {
		node now = pq.top();
		pq.pop();
		if (vst[now.idx][now.cst]) continue;
		if (now.idx == n) {
			cout << now.dst;
			break;
		}
		vst[now.idx][now.cst] = true;
		for (auto nxt : gph[now.idx]) {
			pq.push(node(nxt.first, min(now.cst, cst[nxt.first]), now.cst * nxt.second + now.dst));
		}
	}

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-03-10 12:26

Read more posts by this author