[백준/BOJ] 백준 2611번 : 자동차경주

https://www.acmicpc.net/problem/2611

2611번: 자동차경주

1번 정점에서 출발해서 1번 정점으로 다시 돌아올 때까지 위상 정렬을 해 나아가면서 cache에 해당 지점에서 최대 점수를 저장해 나아가는 방법을 통해 문제를 해결했다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int n;
int m;
vector<pair<int, int>> adj[1001];
vector<int> indegree(1001, 0);
queue<pair<int, int>> q;
vector<int> cache(1001, -1); //[위치] = 해당 위치까지 가는데 얻은 최대 점수
vector<int> from(1001, -1); //[위치] = 해당 위치로 이전에 어디였는지(어느 위치에서 왔는지)
int result1;
vector<int> result2;

//도착지점에서 부터 거꾸로 경로를 찾는다
void Solve(int here)
{
	result2.push_back(here);

	//1에서 부터 왔을때 즉, here이 시작지점에서 처음 나온 지점일때
	if (from[here] == 1)
		result2.push_back(1);

	else
		Solve(from[here]);
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		int p, q, r;
		cin >> p >> q >> r;

		adj[p].push_back(make_pair(r, q));
		indegree[q]++;
	}

	q.push(make_pair(0, 1));

	while (!q.empty())
	{
		int cost = q.front().first;
		int here = q.front().second;
		q.pop();

		//1로 돌아온 경우일때
		if (here == 1 && cost != 0)
		{
			result1 = cost;
			break;
		}

		for (int i = 0; i < adj[here].size(); i++)
		{
			int this_cost = adj[here][i].first;
			int there = adj[here][i].second;

			indegree[there]--;

			//지금 온 경로에서의 점수가 기존의 점수보다 더 클때
			if (cost + this_cost > cache[there])
			{
				cache[there] = cost + this_cost;
				from[there] = here;
			}

			if (indegree[there] == 0)
			{
				q.push(make_pair(cache[there], there));
			}
		}
	}

	Solve(1);
	reverse(result2.begin(), result2.end()); //거꾸로의 경로를 찾은거를 뒤집는다

	cout << result1 << "\n";
	for (int i = 0; i < result2.size(); i++)
	{
		cout << result2[i] << " ";
	}

	return 0;
}