풀이
처음 문제를 보자마자 다익스트라 풀이를 떠올렸는데
문제를 다시 읽어보니 1번 노드를 거치지 않고 다시 원래 노드로 돌아 올 수 없다
이거 싸이클도 없고 완전 DAG잖아?
위상정렬해서 풀려고 했는데
생각해보니 dp로 풀 수 있잖아?
코드
#include <stdio.h>
#include <vector>
using namespace std;
const int n_ = 1000 + 1;
int n, m, dp[n_], route[n_];
vector<pair<int, int> > gph[n_];
int dfs(int now) {
if (!dp[now] && now != 1) for (auto nxt : gph[now]) {
int ret = dfs(nxt.first) + nxt.second;
if (ret > dp[now]) {
dp[now] = ret;
route[now] = nxt.first;
}
}
return dp[now];
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; ++i) {
int p, q, r;
scanf("%d %d %d", &p, &q, &r);
gph[p].push_back(make_pair(q, r));
}
int tmp, ans = 0;
for (auto nxt : gph[1]) {
int ret = dfs(nxt.first) + nxt.second;
if (ret > ans) ans = ret, tmp = nxt.first;
}
printf("%d\n1", ans);
for (int i = tmp; i; i = route[i]) printf(" %d", i);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이