#1504 특정한 최단 경로

특정한 최단 경로는 중간에 두군데의 지점을 반드시 통과하는 경로중 최단 경로를 찾아라하는 문제입니다.

 

중간에 두군데의 지점을 반드시 통과하기 위해서는 [시작]-[지점1]-[지점2]-[끝]을 가는 경로와 [시작]-[지점2]-[지점1]-[끝]을 가는 경로중 거리가 짧은 것을 선택하시면 됩니다.

 

기본적인 알고리즘은 다익스트라(Dijkstra)의 변형입니다.  다익스트라 변형은 도착지점이 큐에서 나오면, 더이상 계산하지 않도록 하는 것입니다.  무방향 그래프이므로 [지점1]-[지점2]와 [지점2]-[지점1]은 같은 값입니다.

 

graph shortest path

 

제가 구현한 소스입니다.  소스는 참조용으로만 봐주세요.

//------------------------------------------------------------------------------
//    baekjoon #1504
//        - by Aubrey Choi
//        - created at 2019-11-07
//------------------------------------------------------------------------------
#include <stdio.h>
#include <queue>
#define    INF 100000000
int adj[800][800], n;
int dijkstra(int s, int e)
{
    std::priority_queue<int, std::vector<int>, std::greater<int> > q;
    int v[800];
    for(int i=0;i<n;i++) v[i]=INF;
    q.push(s); v[s]=0;
    while(!q.empty())
    {
        s=q.top(); q.pop(); int t=s>>16; s&=0xffff;
        if(s == e) break;
        for(int i=0;i<n;i++)
        {
            if(adj[s][i]==0||v[i]<=v[s]+adj[s][i]) continue;
            v[i]=v[s]+adj[s][i]; q.push((v[i]<<16)|i);
        }
    }
    return v[e];
}
int main()
{
    int e, a, b, w, r1, r2;
    scanf("%d%d",&n,&e);
    while(e--)
    {
        scanf("%d%d%d",&a,&b,&w);a--,b--;
        adj[a][b]=adj[b][a]=w;
    }
    scanf("%d%d",&a,&b); a--,b--;
    w=dijkstra(a,b);
    r1=dijkstra(0,a)+dijkstra(b,n-1);
    r2=dijkstra(0,b)+dijkstra(a,n-1);
    if(w>=INF||r1>=INF||r2>=INF) { puts("-1"); return 0; }
    printf("%d\n", (r1<r2?r1:r2)+w);
}