BOJ 1504번 특정한 최단 경로

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

github : https://github.com/junho0956/Algorithm/blob/master/1504/1504/%EC%86%8C%EC%8A%A4.cpp

 

확인해야할 경우는 2가지 입니다.

s -> v1 -> v2 -> e

s -> v2 -> v1 -> e

이 둘중 최솟값을 고르면 됩니다.

이 때 WA를 받게된 사소한 부분이 있는데

INF를 987654321로 두고 문제를 풀 때

한 경로 당 최대 3번까지 INF를 더하게 될 수도 있습니다.

이 때 int 의 범위를 벗어나므로 INF 값을 좀더 작은 값으로 사용해주시거나 (ex:800*1000 이상)

답 받을때만 long long 을 사용해주시면 됩니다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
 
typedef pair<int, int> pii;
#define INF 987654321
 
bool visit[802];
vector<pii> v[802];
priority_queue<pii, vector<pii>, greater<pii> > q;
int N, E, ms, me;
 
vector<int> dijkstra(int start) {
    memset(visit, 0, sizeof(visit));
    vector<int> dist(N+1, INF);
    dist[start] = 0;
    q.push({ 0,start });
 
    while (!q.empty()) {
        int cur = q.top().second;
        int len = q.top().first;
        q.pop();
 
        if (visit[cur]) continue;
        visit[cur] = true;
        
        for (int i = 0; i < v[cur].size(); i++) {
            int vertex = v[cur][i].first;
            int distance = v[cur][i].second;
            if (!visit[vertex] && len + distance < dist[vertex]) {
                dist[vertex] = len + distance;
                q.push({ dist[vertex], vertex });
            }
        }
    }
 
    return dist;
}
 
void solve() {
    cin >> N >> E;
    for (int i = 0; i < E; i++) {
        int s, e, w;
        cin >> s >> e >> w;
        v[s].push_back({ e,w });
        v[e].push_back({ s,w });
    }
    cin >> ms >> me;
 
    vector<int> dist;
 
    long long ans1, ans2;
    dist = dijkstra(1);
    ans1 = dist[ms];
    ans2 = dist[me];
 
    dist = dijkstra(ms);
    ans1 += dist[me];
    ans2 += dist[N];
 
    dist = dijkstra(me);
    ans1 += dist[N];
    ans2 += dist[ms];
 
    long long ans = min(ans1, ans2);
    if (ans >= INF) cout << "-1";
    else cout << ans;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
}