백준(BOJ) 1854 k번째 최단경로

# 다익스트라 # priority queue

기본적인 다익스트라 알고리즘에서는 1에서 출발하여  i도시 까지 도착한 최단거리 하나만 저장하면 되지만,

이 문제는 조금 응용하여 버려지는 거리(최단 거리가 아닌)값 들도 나중에 사용될 수 있기 때문에 저장한다.

즉, update부분에서 모든 경로의 거리에 대해서 저장해야한다.

저장할때 매 k번쨰 최단거리 즉 가장 최소값만 알면되기 때문에 priority_queue를 이용한다.

# 실수 했던 점

순환을 할 수 있다는 것을 생각하지 못했다.(4% 쯤에서 터짐^^)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <climits>
#define MAX 1005
#define INF 2123456789
#define MOD 1000000007
#pragma warning(disable:4996)
using namespace std;
typedef pair<int,int> pi;
typedef long long ll;

int n,m,k,a,b,c,st=1;
int mem[MAX];
bool visit[MAX];
priority_queue<int,vector<int>,greater<int>> pq[MAX];
vector<pi> v[MAX];

int getmin()
// 기본적인 다익스트라와 동일
{
    int ret=-1,mx=INF;
    for(int i=1;i<=n;i++)
        if(!visit[i]&&mem[i]<mx)
            ret=i,mx=mem[i];
    return ret;
}

void update()
{
    for(int i=0;i<v[st].size();i++)
    {
        int next=v[st][i].first;
        int nsum=v[st][i].second+mem[st];
        pq[next].push(nsum);
        // 기본적인 다익스트라와는 달리 모든 경우에 대해서 priority queue로 저장한다.
        if(mem[next]>nsum)
            mem[next]=nsum;
    }
}

void djk()
// 기본적인 다익스트라
{
    while(1)
    {
        st=getmin();
        if(st==-1)break;
        visit[st]=true;
        update();
    }
    
}

int main(void)
{
    scanf("%d%d%d",&n,&m,&k);
    fill_n(&mem[0],MAX,INF);
    mem[st]=0,pq[st].push(0);
    // 처음 1에서 1로 갔을때 경우 0을 추가해준다.
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        v[a].push_back({b,c});
    }
    for(int i=0;i<k;i++)
    {
        djk();
        if(i!=k-1)
        {
            fill_n(&mem[0],MAX,INF);
            fill_n(&visit[0],MAX,0);
            for(int i=1;i<=n;i++)
            // priority queue의 제일 작은 값을 제거한다음.
            // 다익스트라를 다시 시도한다.(경로가 순환인 경우 떄문에) ->4%쯤에 오류 발생
            {
                if(!pq[i].empty())pq[i].pop();
                if(!pq[i].empty())mem[i]=pq[i].top();
            }
        }
    }
    for(int i=1;i<=n;i++)
        if(pq[i].empty())
            printf("-1\n");
        else
            printf("%d\n",pq[i].top());
    return 0;
}