[BOJ] 1504 특정한 최단 경로

문제: https://www.acmicpc.net/problem/1504

 그냥 다익스트라 몇번 돌리면 된다. 어차피 두 정점을 반드시 지나야 하는 것이라면 시작점->1번->2번->종점 아니면 시작점->2번->1번->종점 2가지 방법 안에서 반드시 최단경로는 나오게 되어 있다. 난이도는 1.75/5.

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define INF (100000000)
 
using namespace std;
 
int n;
vector<pair<int,int> > lis[805];
 
vector<int> dijkstra(int x)
{
    vector<int> dist(n+1,INF);
    priority_queue<pair<int,int> > pq;
    dist[x]=0;
    pq.push(make_pair(0,x));
    while(!pq.empty())
    {
        int here=pq.top().second;
        int cost=-pq.top().first;
        pq.pop();
        if(dist[here]<cost) continue;
        for(int i=0;i<lis[here].size();i++)
        {
            int there=lis[here][i].second;
            int tdist=cost+lis[here][i].first;
            if(tdist<dist[there])
            {
                dist[there]=tdist;
                pq.push(make_pair(-tdist,there));
            }
        }
    }
    return dist;
}
 
int main()
{
    int e;
    scanf("%d %d",&n,&e);
    for(int i=0;i<e;i++)
    {
        int t1,t2,w;
        scanf("%d %d %d",&t1,&t2,&w);
        lis[t1].push_back(make_pair(w,t2));
        lis[t2].push_back(make_pair(w,t1));
    }
    int v1,v2;
    scanf("%d %d",&v1,&v2);
    vector<int> a,b,c;
    a=dijkstra(1);
    b=dijkstra(v1);
    c=dijkstra(v2);
    int dist1=a[v1]+b[v2]+c[n];
    int dist2=a[v2]+c[v1]+b[n];
    int ans=min(dist1,dist2);
    if(ans>=INF)
        printf("-1");
    else
        printf("%d",ans);
    return 0;
}