2611 : 자동차경주

풀이

처음 문제를 보자마자 다익스트라 풀이를 떠올렸는데

문제를 다시 읽어보니 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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-02-15 22:51

Read more posts by this author