[BOJ 18780] Timeline

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

18780번: Timeline

 

- 문제 요약

 

Bessie는 지난 M일동안 N개의 착유 회의에 참여했습니다.

하지만, 그녀는 회의에 참여했을 때를 기억하는 것에 어려움을 겪고 있습니다.

i = 1 ... N개의 각 세션에 대해 그 일이 S[i]일 이전에 발생했다는 것을 알고 있으며, 세션에 대한 설명 (a,b,x)가 주어집니다.

(여기서 3개의 정수 쌍 (a,b,x)는 세션 b가 a일 이후에 최소 x일 동안 발생했다는 것을 의미합니다.)

각 착유 세션에 대해서 가능한 가장 이른 날짜를 계산해 주세요.

 

 

- 알고리즘 정리

 

C개의 줄에 입력되는 정수 쌍 (a,b,x)를 활용해서 간선의 가중치를 x로 가지고, a에서 b로 향하는 그래프를 만들어줍니다.

이 그래프에 대해서 위상정렬을 시행해 줍니다.

정렬을 할 때는 a를 오름차순으로 볼 때를 기준으로 진행해 줍니다.

그리고 각 꼭짓점에 대해 Sb=max(Sb, Sa+x)를 기준으로 정렬해 주면 O(N+M) 안에 문제를 해결할 수 있습니다.

 

 

- 코드 작성

#include<bits/stdc++.h>
using namespace std;

#define MAX 100001
int n,m,c,s[MAX],arr[MAX];
bool visited[MAX];
vector<pair<int,int>>v[MAX];
queue<int>q;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m>>c;
	for(int i=1;i<=n;i++){
		cin>>s[i];
	}
	for(int i=0;i<c;i++){
		int aa,bb,cc;
		cin>>aa>>bb>>cc;
		v[aa].push_back({bb,cc});
		arr[bb]++;
	}
	for(int i=1;i<=n;i++){
		if(!arr[i]){
			q.push(i);
		}
	}
	while(q.size()){
		int qf=q.front();
		q.pop();
		visited[qf]=1;
		for(auto &i:v[qf]){
			s[i.first]=max(s[i.first],s[qf]+i.second);
			if(!(--arr[i.first])){
				q.push(i.first);
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<s[i]<<"\n";
	}
}

코드 제출 결과