임계경로 - 1948

//1948 - 임계경로
 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int N, M;
int s, e;
vector<vector<pair<int, int>>> adj;
vector<int> order;
vector<int> change;
vector<bool> seen;
vector<bool> visit;
int cache[10000];
 
void init()
{
    cin >> N >> M;
    for(int i = 0; i<N; ++i)
        cache[i] = -1;
    adj = vector<vector<pair<int, int>>>(N+1);
    order = vector<int>();
    change = vector<int>(N+1);
    visit = vector<bool>(N, false);
    seen = vector<bool>(N+1, false);
    int x, y, r;
    for(int i = 0; i<M; ++i)
    {
        cin >> x >> y >> r;
        adj[x].push_back(make_pair(y, r));
    }
    cin >> s >> e;
}
 
void dfs(int here)
{
    seen[here] = true;
    for(int i = 0; i<adj[here].size(); ++i)
    {
        int there = adj[here][i].first;
        if(!seen[there])
            dfs(there);
    }
    order.push_back(here);
}
 
void topologicalSort()
{
    dfs(s);
    reverse(order.begin(), order.end());
    for(int i = 0; i<N; ++i)
        change[order[i]] = i;
}
 
int dp(int idx)
{
    if(idx == N-1)
        return 0;
    int& ret = cache[idx];
    if(ret != -1)
        return ret;
    int nidx = order[idx];
    for(int i = 0; i<adj[nidx].size(); ++i)
    {
        int there = adj[nidx][i].first;
        int cost = adj[nidx][i].second;
        ret = max(ret, dp(change[there]) + cost);
    }
    return ret;
}
 
int trace(int idx)
{
    if(idx == N-1)
        return 0;
    visit[idx] = true;
    int ret = 0;
    int nidx = order[idx];
    for(int i = 0; i<adj[nidx].size(); ++i)
    {
        int there = adj[nidx][i].first;
        int c = adj[nidx][i].second;
        if(dp(change[there]) + c == dp(idx))
        {
            ++ret;
            if(!visit[change[there]])
                ret += trace(change[there]);
        }
    }
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    init();
    topologicalSort();
    cout << dp(0) << "\n";
    cout << trace(0);
}

 

 

 

 

 

 

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

1948번: 임계경로

 

 

 

 

 

 

임계경로

DAG 그래프에서 시작점에서 끝점까지 가는 경로중 최장거리와, 최장거리 경로에 포함되는 도로의 수를 출력하는 문제입니다.

위상정렬로 정점들을 줄세워 놓은 후, dp를 사용해 최장거리를 구하고, cache배열을 다시 참조해 방문한 도로들을 구했습니다.