1504 특정한 최단 경로

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

반드시 거쳐야 하는 두 개의 정점을 a,b라 하면 1->a->b->n 의 최단 경로와 1->b->a->n의 최단 경로의 길이 중 더 작은 것이 답이다. 각각 다익스트라를 3번씩 돌려주면 된다.

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#define INF 800001
using namespace std;
 
int n,m,u,v,w,a,b,p1,p2,ans;
vector<pair<int,int>> adj[801];
 
int dijkstra(int s,int e)
{
    vector<int> dist(n+1,INF);
    dist[s]=0;
    priority_queue<pair<int,int>> pq;
    pq.push({0,s});
    while(!pq.empty())
    {
        int cost=-pq.top().first;
        int now=pq.top().second;
        pq.pop();
        if(dist[now]<cost) continue;
        for(auto i : adj[now])
        {
            int next=i.first;
            int ndist=cost+i.second;
            if(dist[next]>ndist)
            {
                dist[next]=ndist;
                pq.push({-ndist,next});
            }
        }
    }
    return dist[e];
}
 
int main()
{
    scanf("%d %d",&n,&m);
    while(m--)
    {
        scanf("%d %d %d",&u,&v,&w);
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    scanf("%d %d",&a,&b);
    p1=dijkstra(1,a)+dijkstra(a,b)+dijkstra(b,n);
    p2=dijkstra(1,b)+dijkstra(b,a)+dijkstra(a,n);
    ans=min(p1,p2);
    printf("%d",ans>INF?-1:ans);
    return 0;
}