koitp 48560 K번째 최단 경로(KTHSHORTEST)(C++)

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
3.0 초	512 MB	239	40 (17%)	26

문제

N개의 정점과 M개의 간선으로 이루어진 양방향 그래프가 주어진다. 1번 정점에서 N번 정점까지의 K번째 최단경로를 구하여라. 같은 거리로 N번 정점에 도달해도 중간에 이동하는 방법이 다르면 서로 다른 경로로 간주하며 같은 간선을 여러 번 이용할 수도 있다. 만약 1번 정점에서 N번 정점까지의 경로가 존재하지 않으면 -1을 출력한다.

입력

첫 번째 줄에 정점의 개수 N과 간선의 개수 M, 그리고 K가 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 500,000, 1 ≤ K ≤ 10)

두 번째 줄부터 M개의 줄에 걸쳐 간선의 정보가 입력된다. 간선의 정보는 x, y, z꼴로 주어지며 x에서 y로 가는데, 혹은 y에서 x로 가는데 z의 거리를 가지고 있다는 뜻이다. 간선의 길이는 100,000이하의 숫자이다.

출력

첫 번째 줄에 1번 정점에서 N번 정점으로의 K번째 최단거리를 출력한다. 만약, 경로가 존재하지 않으면 -1을 출력한다.

힌트

c++ code : http://ideone.com/8sbg5V

예제 입력

5 7 5 7 2 1 2 2 1 3 5 1 4 1 2 3 2 3 4 5 2 5 6 3 5 1

예제 출력

6 6

#include    <cstdio>
#include    <queue>
#include    <vector>
#pragma warning(disable:4996)
 
struct comp
{
    bool operator()(std::pair<int, long long>& a, std::pair<int, long long>& b)
    {
        return a.second > b.second;
    }
};
std::vector< std::pair<int, long long> > vtx[111111]; //버텍스 별로 다음 버텍스에 대한 시간
std::priority_queue < std::pair<int, long long>, std::vector<std::pair<int, long long>>, comp > q; //해당 버택스, 해당 버텍스까지 오는 경로 
long long D[111111][22]; //N번쨰 vetex의 K번째 경로 
int N, M, K;
int main()
{
    //init
    scanf("%d%d%d", &N, &M, &K);
 
    for (int i = 1; i <= N; ++i)
    {
        vtx[i].clear();
    }
    for (int i = 1; i <= N; ++i)
    for (int j = 1; j <= K + 1; ++j)
        D[i][j] = -1;
 
    //end init
 
    for (int i = 1; i <= M; ++i)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        vtx[x].push_back(std::make_pair(y, z));
        vtx[y].push_back(std::make_pair(x, z));
        // x -> y // y -> x 두 방향 다 가능하므로 
    }
 
    D[1][1] = 0;
    q.push(std::make_pair(1, 0));
 
    while (!q.empty())
    {
        int vtxNum = q.top().first;
        long long time = q.top().second;
        q.pop();
 
        //K번째 경로가 있고 K번째 경로보다 현재 시간이 더 크면 생각할 필요가 없음. 
        if (D[vtxNum][K] < time && D[vtxNum][K] != -1)
            continue;
 
        for (std::vector<std::pair<int, long long> >::iterator vertex = vtx[vtxNum].begin(); vertex != vtx[vtxNum].end(); ++vertex)
        {
            int i;
            for (i = 1; i <= K + 1; ++i)
            if (D[vertex->first][i] == -1)
                break;
 
            D[vertex->first][i] = time + vertex->second;
            while (i > 1 && D[vertex->first][i] < D[vertex->first][i - 1])
            {
                std::swap(D[vertex->first][i], D[vertex->first][i - 1]);
                i--;
            }
            D[vertex->first][K + 1] = -1;
            if (i <= K)
                q.push(std::make_pair(vertex->first, time + vertex->second));
        }
    }
    printf("%lld", D[N][K]);
 
    return 0;
}
 

일단 문제의 예제는 좀 이상한 것 같다.. 

최단 경로를 구하는 것은 기본적으로 다익스트라(dijkstra) 알고리즘이 있다. 

보통 BOJ의 1854번 K번째 최단경로 라면 다익스트라 알고리즘을 고려해볼 만 하다. (n과 m이 그렇게 크지 않기 때문이다.) 

하지만 이 문제의 경우 간선수 M이 500000이고 N이 100000이므로 대충 계산을 해 보아도 MN번만큼의 연산만 해도 벌써 500억? 번이나 한다. 

500초는 걸린다는 것이다. 

이걸 해결하려면 고민에 고민을 하다가... 도움도 많이 받고 결국 생각해낸 것은 

dynamic programming(사실 이게 다이나믹이 맞는지조차 아직도 감이 잘 안잡힌다...) 

주요 포인트는

1. 36~37라인에서 x->y 뿐만 아니라 y->x방향으로도 edge저장을 해주어야 한다는 것. (vtx 변수에서 vtx[x] = (y, z) 일 때 x->y로의 시간이 z이다.)

2. 51라인에서 시간을 줄이기 위해 이미 k번째 경로가 존재하고 만약 해당 vertex까지의 시간이 k번째 경로의 시간보다 클 경우에는 생각할 필요가 없으므로 넘어간다. 

3.min heap을 이용하여(간선 가중치-시간- 기준) 가장 짧은 경로부터 차례대로 계산해준다. 

사실 도저히 못풀겠어서 저 위의 C++ code를 직접 보면 공부가 안될 것 같은 마음에 대신 봐달라고 하고 어디가 어떻게 문제일까 알려달라고 지인에게 부탁했다.. 

주요 포인트는 3번이었는데 사실 아직도 다 이해한 것 같지는 않다... 상당히 어려운 문제였다.