풀이
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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이