[ICPC] 백준 5719 - 거의 최단 경로

http://icpc.me/5719

Step 1.

최단 경로를 구해보자.

 

다익스트라를 통해 어렵지 않게 구할 수 있다.

 

만약 경로를 못찾으면 거의 최단 경로라는 말 자체에 모순이 있는 것이므로 -1를 출력해주자.

 

노드 간 간선이 최대 하나 존재할 수 있다는 설명과 후술할 step 2를 고려하여 인접행렬로 그래프를 구성하여 구성하자.

 

다익스트라를 통해 구한 시작점부터 각 정점까지의 길이는 따로 저장할 수 있도록 하자.

Step 2.

도착점부터 시작점까지 bfs를 통해 거슬러 올라가도록 한다.

 

올라가는 과정에서 도착점까지의 길이 = 정점 i까지의 길이 + 정점 i와 도착점에 연결된 간선의 길이 를 만족한다면 그 간선은 최단 경로에 포함되는 간선이 된다. 해당 간선으로는 통행할 수 없도록 하자.

 

또한 최단 경로에 포함 된다는 것은 i로 향하는 간선 중에 최단 경로에 포함된 간선이 있다는 뜻이므로 정점 i를 큐에 넣고 아까와 같이 반복하여 시작점에서 탐색이 종료될 수 있도록 하자.

 

거슬러 올라가는 부분에 대한 구현은 killedge 함수에 나타나있다.

 

Step 3.

이렇게 배제할 간선들을 모두 처리하고 다익스트라를 수행하면 거의 최단 경로를 구할 수 있다.(혹은 존재하지 않음을 보일 수 있다.)

 

전체코드 - 본문에 작성한 버전

#include <bits/stdc++.h>

#define fi first
#define se second
#define inf 1000000000

using namespace std;
using pii = pair<int, int>;
using graph = vector<vector<pii>>;

bool sp[500][500];
int am[500][500];
int dist[500];

int dijkstra(int start, int goal);
void killedge(int start, int end);

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    while (n && m)
    {
        memset(sp, 0, sizeof sp);
        fill(&am[0][0], &am[0][0] + 500 * 500, inf);

        int s, e;
        cin >> s >> e;
        
        for (int i = 0; i < m; ++i)
        {
            int go, to, fee;
            cin >> go >> to >> fee;
            
            am[go][to] = fee;
        }
        
        int spath = dijkstra(s, e);
        if (spath == inf)
        {
            cout << "-1\n";
        }
        else
        {
            killedge(s, e);
            spath = dijkstra(s, e);
            cout << (spath == inf ? -1 : spath) << '\n';
        }
        
        cin >> n >> m;
    }
}

int dijkstra(int start, int goal)
{
    fill(dist, dist + 500, inf);
    dist[start] = 0;
    
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, start});
    
    while (pq.size())
    {
        auto cur = pq.top();
        pq.pop();
        
        if (cur.fi > dist[cur.se])
            continue;
        
        for (int i = 0; i < 500; ++i)
        {
            if (sp[cur.se][i] || am[cur.se][i] == inf || dist[i] <= cur.fi + am[cur.se][i])
                continue;
            
            dist[i] = cur.fi + am[cur.se][i];
            pq.push({dist[i], i});
        }
    }
    
    return dist[goal];
}

void killedge(int start, int end)
{
    queue<int> q;
    q.push(end);
    
    while (q.size())
    {
        int cur = q.front();
        q.pop();
        
        if (cur == start)
            continue;
        
        for (int i = 0; i < 500; ++i)
        {
            if (dist[cur] == inf || dist[i] == inf || am[i][cur] == inf || sp[i][cur])
                continue;
            
            if (dist[cur] == dist[i] + am[i][cur])
            {
                q.push(i);
                sp[i][cur] = true;
            }
        }
    }
}

전체코드 - 인접리스트를 이용한 구현 (메모리 측면에서 더 우수하다.)

#include <bits/stdc++.h>

#define fir first
#define seco second
#define inf 1000000000

using namespace std;
using pii = pair<int, int>;
using graph = vector<vector<pii>>;

bool sp[500][500];
int dist[500];

int dijkstra(graph &al, int start, int goal);
void build(graph &al, int start, int end);

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    while (n && m)
    {
        memset(sp, 0, sizeof sp);

        int s, e;
        cin >> s >> e;
        
        graph adj(n), revflow(n);
    
        for (int i = 0; i < m; ++i)
        {
            int go, to, fee;
            cin >> go >> to >> fee;
        
            adj[go].push_back({fee, to});
            revflow[to].push_back({-fee, go});
        }
        
        int spath = dijkstra(adj, s, e);

        if (spath == inf)
        {
            cout << "-1\n";
        }
        else
        {
            build(revflow, s, e);
            spath = dijkstra(adj, s, e);
            
            cout << (spath == inf ? -1 : spath) << '\n';
        }
        
        cin >> n >> m;
    }
}

int dijkstra(graph &al, int start, int goal)
{
    fill(dist, dist + 500, inf);
    dist[start] = 0;
    
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, start});
    
    while (pq.size())
    {
        auto cur = pq.top();
        pq.pop();
        
        if (cur.fir > dist[cur.seco])
            continue;
        
        for (auto &item: al[cur.seco])
        {
            if (cur.fir + item.fir >= dist[item.seco] || sp[cur.seco][item.seco])
                continue;
            
            dist[item.seco] = cur.fir + item.fir;
            pq.push({dist[item.seco], item.seco});
        }
    }
    
    return dist[goal];
}

void build(graph &al, int start, int end)
{
    queue<int> q;
    q.push(end);
    
    while (q.size())
    {
        auto cur = q.front();
        q.pop();
        
        if (cur == start)
            continue;
        
        for (auto item: al[cur])
        {
            if (dist[cur] == inf || dist[item.seco] == inf || sp[item.seco][cur])
                continue;
            
            if (dist[cur] + item.fir == dist[item.seco])
            {
                q.push(item.seco);
                sp[item.seco][cur] = true;
            }
        }
    }
}

 

간선이 빽빽히 들어있는 그래프 데이터에 의해 MLE를 받고 솔루션을 다시 작성했다.