5719번

5719번 - 거의 최단 경로

이 문제 푸는데 계속 틀려서, 틀린 테스트 케이스를 찾아보면서 고쳤다.

처음에는 정점을 삭제하는 방식으로 구했더니, 예외가 발생했고.

그래서 간선을 삭제하는 방식으로 풀었더니 또 다른 예외가 발생했다..

단순히 다익스트라를 한번 돌리고, 다시 돌려서 다른 값이 나온다고 정답이 아니었다.

갈 수 있는 최단거리를 모두 가보고, 간선을 삭제하고, 그 다음에 다익스트라로 마지막 답을 구하는 순서로 풀어야 했다.

그래서 처음에 다익스트라를 돌리고, 그 때 간선들 모두 삭제하고, 다익스트라 돌리고, 삭제하고 이런 방법으로 했는데..

삭제 할때도 막 삭제하면 안되는 반례가 존재했다.

어떤 정점에서 나가는 간선이 여러개 일때는, 그 정점을 기준으로 시작점 쪽으로의 간선은 더 이상 지우면 안된다. 

즉 한 정점에서 outdegree 를 하나 지우고도, outdegree 가 있다면, 그 정점에서 indegree 간선부터 시작점까지 지우면 안된다.

그렇게 풀었는데 또 오류가 발생!

지우면 안되지만, 최단거리를 다 찾고는 지워야 한다는 문제가 있었다. 따라서 방문했지만 지우지 않은 간선들을 del 큐에 넣어서 나중에 지웠다.

이 방법이 맞는 방법인지는 모르겠다.. 더 쉬운 방법이 존재할 지는... 

하지만 나름 열심히 생각해보고 풀어서 맞아서 기분은 좋다.. 다른 분들 코드도 훔쳐봐야지

###

다른 분들 코드를 보니, 다익스트라를 2번만 써서 구했다.

일단 한번 써서, 각 정점들의 dist 를 구했다. 그리고 도착점에서부터 시작점까지 dfs 나 bfs 를 통해서 간선을 삭제했다.

간선 삭제할 때 조건은 dist[D] == dist[parent[D]] + w 였다.

이런식으로 하면 모든 간선을 지울 수 있고, 그 다음 다익스트라를 다시 돌려서 정답을 구했다.

<정답 코드>

#include<iostream>
#include<queue>
#include<vector>
#include<string.h>
 
using namespace std;
const int INF = 987654321;
bool check[501][501];
int outdegree[501];
int indegree[501];
int n, m, S, D;
queue<pair<int, int>> del;
void dijkstra(int start,vector<vector<pair<int,int>>> &v)
{
    int chk = -1;
 
    //최단거리를 모두 구하는 2중 while 문, 다익스트라 알고리즘
    while (true)
    {
        priority_queue<pair<int, int>> q;
        vector<int> dist(n, INF);
        dist[start] = 0;
        q.push({ start,dist[start] });
        vector<int> parent(1001, -1);
 
        //최단거리 찾는 다익스트라 알고리즘
        while (!q.empty())
        {
            int now = q.top().first;
            int cost = -q.top().second;
            q.pop();
 
            if (cost > dist[now]) { continue; };
 
            for (int i = 0; i < v[now].size(); i++)
            {
                int next = v[now][i].first;
                int w = v[now][i].second;
 
                if (dist[next] > cost + w && !check[now][next])
                {
                    dist[next] = cost + w;
                    parent[next] = now;
                    q.push({ next,-dist[next] });
                }
            }
        }
 
 
        //맨 처음 다익스트라를 돌렸을 때
        if (chk == -1)
        {
            //처음부터 도착점에 갈 수 없을때
            if (dist[D] >= INF)
            {
                printf("-1\n");
                return;
            }
            //처음에 도착점에 도달했을 때
            else
            {
                //chk 에 최단거리 저장
                chk = dist[D];
                int k = D;
                //부모값들을 올라가면서 outdegree 값이 0이하면 간선 삭제, 1 이상이면 간선 살려두기
                while (parent[k] != -1)
                {
                    outdegree[k]--;
                    if (outdegree[k] <= 0)
                    {
                        check[parent[k]][k] = true;
                    }
                    // 삭제해야하지만, 또 쓸 수 있어서 살려둔 간선들 del 큐에 저장
                    else
                    {
                        del.push({ parent[k],k });
                    }
                    k = parent[k];
                }
                continue;
            }
        }
        // 2번째,3번째,...다익스트라 돌리기
        else
        {
            //첫번째 다익스트라 값이랑 같을 때, 기존 최단거리 말고, 다른 최단거리를 구헀을 때
            if (chk == dist[D])
            {
                int k = D;
                while (parent[k] != -1)
                {
                    outdegree[k]--;
                    if (outdegree[k] <= 0)
                    {
                        check[parent[k]][k] = true;
                    }
                    else
                    {
                        del.push({ parent[k],k });
                    }
                    k = parent[k];
                }
 
                continue;
            }
            
        }
 
 
        //만약 첫번째 다익스트라 값이랑 다르면, 
        break;
    }
 
    //지우지 않았던 간선들 삭제.
    while (!del.empty())
    {
        int a = del.front().first;
        int b = del.front().second;
        del.pop();
        check[a][b] = true;
    }
 
    //다익스트라 알고리즘 다시 돌리기
    priority_queue<pair<int, int>> q;
    vector<int> dist(n, INF);
    dist[start] = 0;
    q.push({ start,dist[start] });
    vector<int> parent(1001, -1);
 
    while (!q.empty())
    {
        int now = q.top().first;
        int cost = -q.top().second;
        q.pop();
 
        if (cost > dist[now]) { continue; };
 
        for (int i = 0; i < v[now].size(); i++)
        {
            int next = v[now][i].first;
            int w = v[now][i].second;
 
            if (dist[next] > cost + w && !check[now][next])
            {
                dist[next] = cost + w;
                parent[next] = now;
                q.push({ next,-dist[next] });
            }
        }
    }
 
    if (dist[D] >= INF)
    {
        printf("-1\n");
    }
    else
    {
        printf("%d\n", dist[D]);
    }
 
 
}
int main()
{
    //freopen("input.txt", "r", stdin);
    while (scanf("%d %d", &n, &m)&& n!=0 && m!=0)
    {
        scanf("%d %d", &S, &D);
        int ans = 0;
        memset(check, false, sizeof(check));
        vector < vector<pair<int, int>>> v(n);
 
    
 
        for (int i = 0; i < m; i++)
        {
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);
            v[a].push_back({ b,c });
            outdegree[a]++;
        }
 
 
        dijkstra(S, v);
    }
 
    return 0;
}