백준 1948 - 임계경로.

/*
백준 1948번. 위상정렬이용.
모든임계경로를 다 구해야 하므로 역추적을 수행해야함.
*/

/*
첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 
그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 
처음에는 도로의 출발 도시의 번호가 주어지고 그 다음에는 도착 도시의 번호, 
그리고 마지막에는 이 도로를 지나는데 걸리는 시간이 주어진다. 
도로를 지나가는 시간은 10,000보다 작거나 같은 자연수이다.
그리고 m+3째 줄에는 지도를 그리는 사람들이 출발하는 출발 도시와 도착 도시가 주어진다.
모든 도시는 출발 도시로부터 도달이 가능하고, 모든 도시로부터 도착 도시에 도달이 가능하다.
*/

#include<iostream>
#include<vector>
#include<queue>
#define MAX 10001

using namespace std;

class Edge
{
public:
	int node;
	int time;

	Edge(int node, int time)
	{
		this->node = node;
		this->time = time;
	}
};

int n, start, finish;
int inDegree[MAX], result[MAX], c[MAX];
vector<Edge> a[MAX];
vector<Edge> b[MAX];

void topologySort()
{
	queue<int> q;
	//시작점 노드를 큐에 삽입.
	q.push(start);
	//더이상 방문할 노드가 없을 때까지
	while (!q.empty())
	{
		int x = q.front();
		q.pop();

		for (int i = 0; i < a[x].size(); i++)
		{
			Edge y = Edge(a[x][i].node, a[x][i].time);

			if (result[y.node] <= y.time + result[x])
			{
				result[y.node] = y.time + result[x];
			}
			//새롭게 진입차수가 0이 된 정점을 큐에 삽입.
			if (--inDegree[y.node] == 0)
			{
				q.push(y.node);
			}
		}
	}
	//결과를 역추적.
	int count = 0;
	q.push(finish);

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

		for (int i = 0; i < b[y].size(); i++)
		{
			Edge x = Edge(b[y][i].node, b[y][i].time);
			//최장 경로에 포함되는 간선인지 확인.
			if (result[y] - result[x.node] == x.time)
			{
				count++;
				//큐에는 한 번씩만 담아 추적.
				if (c[x.node] == 0)
				{
					q.push(x.node);
					c[x.node] = 1;
				}
			}
		}
	}

	cout << result[finish] << endl << count;
}

int main()
{
	int m;

	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		int x, node, time;

		cin >> x >> node >> time;

		a[x].push_back(Edge(node, time));
		b[node].push_back(Edge(x, time));
		inDegree[node]++;
	}

	cin >> start >> finish;

	topologySort();
}