백준 1504번 특정한 최단 경로

백준 1504번 특정한 최단 경로

#include <iostream>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAX 10000+1
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 387654321;
vector<pii > adj[801];
int dist[900];
bool visited[900];
int V, E;
int p, q;
void dijk(int start) {
    fill(dist, dist + V + 1, INF);
    memset(visited, 0, sizeof(visited));
    dist[start] = 0;
    priority_queue<pii, vector<pii>, greater<pii> > pq;
    pq.push({ 0,start });
    while (!pq.empty()) {
        pii t = pq.top();
        pq.pop();
        int here = t.second;
        int cost = t.first;
        if (dist[here] != cost) continue; // dist[here] < cost인 경우만 존재.
        for (pair<int, int> &p : adj[here]) {
            int there = p.first;
            int there_cost = p.second;
            if (dist[there] > cost + there_cost) {
                dist[there] = cost + there_cost;
                pq.push({ cost + there_cost,{there} });
            }
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> V >> E;
    for (int i = 0; i < E; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({ b,c });
        adj[b].push_back({ a,c });
    }
    cin >> p >> q;
    dijk(1);
    int a = dist[p];            //1에서 p까지
    int b = dist[q];            //1에서 q까지
    dijk(p);
    int c = dist[q];            //p에서 q까지 or q에서 p까지
    int d = dist[V];            //p에서 N까지 
    dijk(q);
    int e = dist[V];            //q에서 N까지
    int Min = 0;
    
    Min = min(a + c + e, b + c + d);
    if (Min >= INF) {
        cout << -1; return 0;
    }
    cout << Min;
 
    return 0;
 
}

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

특정한 두 점을 지나는 경우를 따로 다익스트라를 돌려서 풀 수 있는 문제였습니다.

a+c+e, b+c+d 둘다 INF가 987654321 일 때 오버플로우가 발생 할 수 있는 경우를 고려해서 

INF값을 좀 낮춰주니 AC를 받았습니다.