임계경로 1948

문제

접근 방법

두 부분으로 나눠서 볼 수 있다.

이 지도를 그리는 사람들은 사이가 너무 좋아서 지도를 그리는 일을 다 마치고 도착 도시에서 모두 다 만나기로 하였다. 그렇다고 하였을 때 이들이 만나는 시간은 출발 도시로부터 출발한 후 최소 몇 시간 후에 만날 수 있는가? 즉, 마지막에 도착하는 사람까지 도착을 하는 시간을 의미한다.

도착 도시까지의 최대 시간을 의미한다.
최대 시간은 직접 탐색해서 확인해 주면 된다.

어떤 사람은 이 시간에 만나기 위하여 1분도 쉬지 않고 달려야 한다. 이런 사람들이 지나는 도로의 수를 카운트 하여라.

최대 시간이 걸릴 때 해당하는 사람들이 사용한 도로를 중복 없이 세어주면 된다.
사용한 도로는 부모를 갱신하여 확인하거나 값을 거슬러 올라가는 방식으로 가능하다.

코드

#include <iostream>
#include <queue>
#include <vector>
#include <tuple>
using namespace std;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;
int n, m, startCity, endCity;
vector<vector<pii>> startGraph;
vector<vector<int>> parents;
vector<int> isVisited;
void input()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    startGraph = vector<vector<pii>>(n + 1, vector<pii>());
    isVisited = vector<int>(n + 1, -1);
    parents = vector<vector<int>>(n + 1, vector<int>());
    while (m--)
    {
        int city1, city2, time;
        cin >> city1 >> city2 >> time;
        startGraph[city1].push_back({time, city2});
    }
    cin >> startCity >> endCity;
}
void dijkstra()
{
    priority_queue<tiii> pq;
    pq.push({0, startCity, 0});
    while (!pq.empty())
    {
        tiii cur = pq.top();
        pq.pop();
        int value = get<0>(cur);
        int index = get<1>(cur);
        int parent = get<2>(cur);
        if (isVisited[index] != -1 && isVisited[index] >= value)
        {
            if (isVisited[index] == value)
                parents[index].push_back(parent);
            continue;
        }
        parents[index].clear();
        parents[index].push_back(parent);
        isVisited[index] = value;
        for (pii node : startGraph[index])
        {
            if (isVisited[node.second] != -1 && isVisited[node.second] > isVisited[index] + node.first)
                continue;
            pq.push({value + node.first, node.second, index});
        }
    }
}
int dfs(int cur)
{
    if (cur == startCity || !isVisited[cur])
        return 0;
    isVisited[cur] = 0;
    int ret = 0;
    for (int next : parents[cur])
        ret += dfs(next) + 1;
    return ret;
}
int main()
{
    input();
    dijkstra();
    cout << isVisited[endCity] << "\n";
    cout << dfs(endCity);
    return 0;
}

풀이

도착 도시까지의 최대 시간을 구하는 방법으론 다익스트라와 위상 정렬이 있다.
사이클이 없는 방향 그래프이기에 위상 정렬을 사용하는 것이 좋다.

부모를 갱신하는 경우에는 같은 값으로 도착한 경우에는 추가해 주고 더 높은 값으로 도착한 경우에는 초기화하고 추가해 준다.
값을 거슬러 올라가는 경우에는 역방향 그래프를 추가하여야 하고 현재 지점에서 다음 지점으로 갈 때 비용을 빼주면 값이 일치하는지 확인해야 한다.