[백준/BOJ] 백준 18780번 : Timeline

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

18780번: Timeline

 

세션 사이의 관계를 그래프로 만들고, 그래프를 위상정렬 하며 배열 s에 s[세션 번호] = 해당 세션이 최소 며칠 이후에 일어나는지를 저장해 나아가는 방법으로 문제를 해결했다.

 

코드

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

int n, m, c;
int s[100005]; //s[i] = i 세션이 최소 몇일 이후에 일어나는지
vector<pair<int, int>> adj[100005];
int indegree[100005];

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

	cin >> n >> m >> c;

	for (int i = 1; i <= n; i++) {
		int input;
		cin >> input;
		s[i] = input;
	}

	for (int i = 0; i < c; i++) {
		int a, b, x;
		cin >> a >> b >> x;

		adj[a].push_back(make_pair(x, b));
		indegree[b]++;
	}

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

	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;

			s[there] = max(s[there], s[here] + cost); //there 세션이 최소 몇일 이후에 일어나는지 더 큰값으로 갱신
			indegree[there]--;

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

	for (int i = 1; i <= n; i++) {
		cout << s[i] << "\n";
	}

	return 0;
}