[백준] 2611 자동차 경주

문제

자동차 경주로는 <그림 1>의 예와 같이 표현된다. 화살표는 각 지점을 잇는 도로를 의미하며 모든 도로는 일방통행 도로로 화살표 방향으로만 움직일 수 있다.

자동차 경주의 코스는 1번 지점에서 출발하여 다시 1번 지점으로 되돌아오는 것이다. 단, 중간에는 1번 지점을 지나서는 안 된다. 경주로는 1번 지점을 제외한 어느 지점에서 출발하여도 1번 지점을 지나가지 않고서는 같은 지점으로 돌아올 수 없도록 되어 있다. 또한 1번 지점에서 다른 모든 지점으로 갈 수 있고, 다른 모든 지점에서 1번 지점으로 갈 수 있다.

각 도로에는 <그림 2>의 예와 같이 그 도로를 지날 때 얻는 점수가 있다.

1번 지점에서 출발하여 가장 많은 점수를 얻어 다시 1번 지점으로 돌아오는 팀이 우승을 하게 된다. 가장 많은 점수를 얻어 1번 지점으로 돌아오는 경로를 찾아 그 얻는 점수와 경로를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 지점의 개수 N이 주어진다. 각 지점에는 1부터 N까지의 서로 다른 번호가 부여된다. 둘째 줄에는 도로의 개수 M이 주어진다. 이어 M개의 줄에는 p ,q ,r의 형식으로 도로의 정보가 주어지는데 이는 p번 지점부터 q번 지점으로 갈 수 있는 도로가 있고 그 도로에 부여된 점수가 r이라는 뜻이다. N은 1000이하의 자연수이고, p와 q는 1이상의 N이하의 자연수이며 r은 100이하의 자연수 이다. p와 q는 같지 않다.

출력

가장 많은 점수를 얻은 경로를 찾아, 첫째 줄에는 그 얻는 점수를 출력하고 둘째 줄에는 그 경로를 출력한다. 경로를 출력할 때는 지나는 지점들의 번호를 사이에 한 칸의 공백을 두어 출력한다. 출력하는 경로는 반드시 1번 지점에서 시작하여 1번 지점으로 끝나야 한다. 만약 같은 점수를 얻는 경로가 둘 이상일 경우 그 중 하나만 출력하면 된다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL)
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 };

int N, M, p, q, r, dp[1001], n[1001], pa[1001], v[1001];
vector<pi> adj[1001];
void print(int k) {
	if (v[k])return;
	v[k] = 1;
	print(pa[k]);
	cout << k << " ";
}
int main() {
	FAST;
	cin >> N >> M;
	while (M--) {
		cin >> p >> q >> r;
		adj[p].push_back({ q,r });
		n[q]++;
	}
	queue<int>q;
	q.push(1);
	while (!q.empty()) {
		auto t = q.front(); q.pop();
		if (t == 1 && dp[1])break;
		for (auto [nxt, cost] : adj[t]) {
			if (dp[nxt] <= dp[t] + cost) {
				dp[nxt] = dp[t] + cost;
				pa[nxt] = t;
			}
			if (!(--n[nxt]))
				q.push(nxt);
		}
	}
	cout << dp[1] << "\n1 ";
	print(1);
}

DP와 위상정렬을 이용합니다.

1부터 시작해서 도착할 수 있는 정점에 대해서 

dp[next]=max(dp[next],dp[cur]+dist)를 수행합니다.

모든 들어오는 간선에 대해서 최댓값을 저장합니다. 그리고  그 최댓값에 대해 부모노드를 저장합니다.