[백준/BOJ] 백준 1948번 : 임계경로

www.acmicpc.net/problem/1948

1948번: 임계경로

Long_len함수를 통해 start에서 dest까지 다익스트라 알고리즘을 활용하여 최장거리(최장 시간)를 구한다 그때, come_from[there]을 상황에 따라 추가하거나, 지우고 추가하는 방식으로 경로를 저장한 뒤, Count함수에서 이렇게 만들어진 그래프를 통해 포함된 도로의 수를 구한다.

 

코드

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

int n, m;
vector<pair<int, int>> adj[10001];
vector<int> come_from[10001];

int Long_len(int start, int dest) //start에서 dest까지 최장거리(최장 시간)을 구한다.
{
	priority_queue<pair<int, int>> pq;
	vector<int> result(n + 1, -1);

	result[start] = 0;
	pq.push(make_pair(0, start));

	while (!pq.empty())
	{
		int here = pq.top().second;
		int here_cost = pq.top().first;
		pq.pop();

		if (here_cost < result[here])
			continue;

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

			if (result[there] <= there_cost) //지금까지 발견된 거리(시간) 이상의 there일때
			{
				if (result[there] == there_cost)
				{
					come_from[there].push_back(here); //there로 온 지점을 저장
				}

				else if (result[there] < there_cost)
				{
					result[there] = there_cost;

					come_from[there].clear(); //이전 정보 지우기
					come_from[there].push_back(here); //there로 온 지점을 저장

					pq.push(make_pair(there_cost, there));
				}
			}
		}
	}

	return result[dest];
}

//dest에서 start로 거꾸로 가며 포함된 도로의 수를 센다
int Count(int dest, int start)
{
	int cnt = 0;

	vector<int> discovered(n + 1, 0);
	queue<int> q;
	
	discovered[dest] = 1;
	q.push(dest);

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

		if (here == start) //start지점일때
			continue;

		for (int i = 0; i < come_from[here].size(); i++)
		{
			int there = come_from[here][i];

			cnt++;

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

	return cnt;
}

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

	int s, d, t;
	int start, dest;

	cin >> n >> m;

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

		adj[s].push_back(make_pair(t, d));
	}

	cin >> start >> dest;

	int long_len = Long_len(start, dest);
	int cnt = Count(dest, start);

	cout << long_len << "\n";
	cout << cnt << "\n";

	return 0;
}