[C++] 백준 1504 - 특정한 최단 경로

1504번: 특정한 최단 경로

풀이

1. 첫노드→N1 로가는 짧은경로 + N1 → N2로가는 경로 + N2에서 n번째노드로 가는 경로

2. 첫노드→N2 로가는 짧은경로 + N2 → N1로가는 경로 + N1에서 n번째노드로 가는 경로

둘중 짧은 것이 답이다.

 

 

코드

#include <bits/stdc++.h>

using namespace std;

vector<pair<int,int>> adj[801];

int n,e;
int v1,v2;

int Dijkstra(int src, int nend){
   vector<int> dist(801, 100000000);
   dist[src] = 0;
   priority_queue<pair<int,int>> q;
   q.push(make_pair(0,src));
   
   while(!q.empty()){
       int cost = -q.top().first;
       int node = q.top().second;
       q.pop();
       
       if(dist[node] < cost) continue;
       
       for(int i = 0; i < adj[node].size(); i++){
           int nextNode = adj[node][i].first;
           int nextCost = adj[node][i].second + cost;
           
           if(dist[nextNode] > nextCost){
               dist[nextNode] = nextCost;
               q.push(make_pair(-nextCost, nextNode));
           }
       }
   }
   return dist[nend];
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> e;
    int b,nb,c;
    for(int i =0 ; i < e; i++){
        cin >> b >> nb >> c;
        adj[b].push_back(make_pair(nb,c));
        adj[nb].push_back(make_pair(b,c));
    }
    cin >> v1 >> v2;
    int answer = 100000000;
    answer = min(answer, Dijkstra(1,v1) + Dijkstra(v1,v2) + Dijkstra(v2,n));
    answer = min(answer, Dijkstra(1,v2) + Dijkstra(v2,v1) + Dijkstra(v1,n));
   if(answer != 100000000)
   cout << answer;
   else
   cout << -1;
    return 0;
}