[백준/BOJ] 백준 16064번 : Coolest Ski Route

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

16064번: Coolest Ski Route

 

위상 정렬을 통해 경로의 이동으로 얻어지는 최대 상태 합을 구해서 문제를 해결했다

 

코드

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

int n, m;
vector<pair<int, int>> adj[1005];
int indegree[1005];
int max_sum[1005];

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

	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int s, t, c;
		cin >> s >> t >> c;

		adj[s].push_back(make_pair(c, t));
		indegree[t]++;
	}

	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (indegree[i] == 0) {
			q.push(i);
			max_sum[i] = 0;
		}
	}

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

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

			indegree[there]--;
			max_sum[there] = max(max_sum[there], max_sum[here] + cost);

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

	int result = 0;
	for (int i = 1; i <= n; i++) {
		result = max(result, max_sum[i]);
	}
	cout << result;

	return 0;
}