[BOJ 1948] 임계경로

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

1948번: 임계경로

---

위 문제는 위상 정렬을 통해서 만나는 최소의 값과 해당 값으로 도달할 수 있는 간선의 개수를 구하는 문제이다. 

 

처음에 도로의 수가 무엇을 의미하는지 몰라 조금 헤맸었다.

 

입력 예제를 그래프로 표현했을 때 아래와 같이 나오며, 빨간색으로 된 간선이 정답이 되는 간선의 수와 값이다.

 

최솟값을 구하는 방법은 위상 정렬을 통해서 구하면 되지만 간선의 개수는 따로 구하였다.

 

위상 정렬을 할 때마다 값이 경신될 때마다 갱신되는 노드로 가는 간선을 따로 저장해 두고 이들의 개수를 세는 방법으로 계산하였다.

 

즉, 각 노드별로 도착시간을 갱신하게 되는데 이때 갱신된 값으로 올 수 있는 경로를 노드마다 저장해 놓고 나중에 도착 도시부터 이를 차례로 세면서 개수를 저장했다. 

 

노드의 간선이 중복으로 세어지는 것을 방지하기 위해 간선이 세어졌는지를 따로 확인하면서 풀었다.

---

#include <stdio.h>
#include <vector>
#include <queue>

struct Info
{
	int dst, v;
	bool b;
};

using namespace std;

int n, m;
int indgree[10001];
int ans[10001];
int cnt;
int st, ed;
vector<vector<Info>> g;
vector<vector<int>> pre;

bool f(int s, int p)
{
	for (auto t = g[s].begin(); t != g[s].end(); t++)
	{
		if ((*t).dst == p)
		{
			if ((*t).b)
			{
				(*t).b = false;
				return true;
			}
			else
				return false;
		}
	}
	return false;
}

int main()
{
	int ansCnt = 0;
	scanf("%d%d", &n, &m);
	g.resize(n + 1);
	pre.resize(n + 1);
	for (int i = 0; i < m; i++)
	{
		int a, b, v;
		scanf("%d%d%d", &a, &b, &v);
		g[a].push_back({ b,v, true});
		indgree[b]++;
	}
	scanf("%d%d", &st, &ed);

	queue<int> q;

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

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

		for (auto s = g[p].begin(); s != g[p].end(); s++)
		{
			if (--indgree[(*s).dst] == 0)
				q.push((*s).dst);
			if ((*s).v + ans[p] > ans[(*s).dst])
			{
				ans[(*s).dst] = (*s).v + ans[p];
				pre[(*s).dst].clear();
			}

			if ((*s).v + ans[p] == ans[(*s).dst])
				pre[(*s).dst].push_back(p);
		}
	}


	int cnt = 0;
	q.push(ed);
	while (!q.empty())
	{
		int p = q.front(); q.pop();

		for (auto s = pre[p].begin(); s != pre[p].end(); s++)
		{
			if (f(*s, p))
			{
				q.push(*s);
				cnt++;
			}
		}
	}

	printf("%d\n%d", ans[ed],cnt);
}