백준 2176 - 합리적인 이동경로

www.acmicpc.net/problem/2176

 

솔루션 1.

모든 정점 사이의 최단 경로를 구한 다음 그래프 DP를 수행하면서 "합리적인 이동경로"를 탐색하면 간단하게 AC를 받을 수 있다.

 

전체 코드

#include <bits/stdc++.h>
 
using namespace std;
using pii = pair<int, int>;
using graph = vector<vector<pii>>;
 
int n, m;
int dist[1001][1001];
int dp[1001];
 
int dijkstra(int start, graph &al);
int memo(int v, graph &al);
 
int main()
{
    memset(dp, -1, sizeof dp);
    fill(&dist[0][0], &dist[0][0] + 1001 * 1001, numeric_limits<int>::max());
    ios::sync_with_stdio(false); cin.tie(0);
 
    cin >> n >> m;
 
    graph adj(n + 1);
    
    for (int i = 0; i < m; ++i)
    {
        int go, to, fee;
        cin >> go >> to >> fee;
        adj[go].push_back({to, fee});
        adj[to].push_back({go, fee});
    }
 
    for (int i = 1; i <= n; ++i)
        dijkstra(i, adj);
 
    cout << memo(1, adj);
}
 
int dijkstra(int start, graph &al)
{
    priority_queue<pii, vector<pii>, greater<pii>> pq;
 
    pq.push({0, start});
    dist[start][start] = 0;
 
    while (pq.size())
    {
        auto cur = pq.top();
        pq.pop();
 
        if (cur.first > dist[start][cur.second])
            continue;
 
        for (auto item: al[cur.second])
        {
            int ndist = cur.first + item.second;
            
            if (ndist < dist[start][item.first])
            {
                dist[start][item.first] = ndist;
                pq.push({ndist, item.first});
            }
        }
    }
 
    return dist[start][2];
}
 
int memo(int v, graph &al)
{
    if (v == 2)
        return 1;
 
    int &ret = dp[v];
 
    if (ret != -1)
        return ret;
    
    ret = 0;
 
    for (auto item: al[v])
        if (dist[v][2] > dist[item.first][2])
            ret += memo(item.first, al);
    
    return ret;
}

 

솔루션 2.

DP를 최단 경로를 탐색하면서 수행한다.

 

다익스트라를 기준으로 설명한다.

 

다음 dp 테이블을 최단 경로를 찾아가면서 채울 것이다.

 

dp[i] = i번 노드에서 출발하는 합리적인 이동경로의 수

 

거꾸로 도착점 2번 노드부터 탐색을 시작한다.

 

각 정점까지의 최단 경로를 갱신하는 과정에서

현재 노드까지 최단 경로의 길이 > 다음 노드까지 최단 경로의 길이라면 다음 노드와 현재 노드 사이에 "합리적인 이동경로"가 존재한다는 뜻이 된다. (최단 경로를 역방향으로 탐색하고 있음을 유의하자.)

 

이를 만족하면 점화식 dp[현재 노드] += dp[다음 노드]을 통해 최종적으로 1번 노드에서 출발하는 합리적인 이동경로의 수를 구할 수 있다.

 

dp 진행 예시 : 2번 노드와 1번 노드만 있고 둘이 연결되어 있다고 하자.

 

1. 2번 노드에서 탐색 후 1번 노드를 큐에 삽입

 

2. 큐에 꺼낸 1번 노드는 2번 노드와 합리적인 이동경로가 존재하므로 2번에서 출발했을 때 합리적인 이동경로의 수를 1번 노드에 합산하면 테이블을 채울 수 있다.

 

전체 코드

#include <bits/stdc++.h>
 
using namespace std;
using pii = pair<int, int>;
using graph = vector<vector<pii>>;
 
int n, m;
int dist[1001];
int dp[1001];
 
void dijkstra(graph &al);
 
int main()
{
    fill(dist, dist + 1001, numeric_limits<int>::max());
    ios::sync_with_stdio(false); cin.tie(0);
 
    cin >> n >> m;
 
    graph adj(n + 1);
    
    for (int i = 0; i < m; ++i)
    {
        int go, to, fee;
        cin >> go >> to >> fee;
        adj[go].push_back({to, fee});
        adj[to].push_back({go, fee});
    }
 
    dijkstra(adj);
    cout << dp[1];
}
 
void dijkstra(graph &al)
{
    priority_queue<pii, vector<pii>, greater<pii>> pq;
 
    pq.push({0, 2});
    dist[2] = 0;
    dp[2] = 1;
 
    while (pq.size())
    {
        auto cur = pq.top();
        pq.pop();
 
        if (cur.first > dist[cur.second])
            continue;
        
        for (auto item: al[cur.second])
        {
            int ndist = item.second + cur.first;
 
            if (ndist < dist[item.first])
            {
                dist[item.first] = ndist;
                pq.push({ndist, item.first});
            }
 
            if (cur.first > dist[item.first])
                dp[cur.second] += dp[item.first];
        }
    }
}
 

 

탐색 후 DP를 수행한 솔루션 1이 비교적 느린 결과를 보여준다.