Baekjoon 1504번 특정한 최단 경로

문제

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

걸린 시간

00 : 37 : 32

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, e;
    cin >> n >> e;
    vector<vector<ll>> adj(n, vector<ll>(n, INF));
    int a, b, c;
    for(int i = 0; i < e; i++){
        cin >> a >> b >> c;
        adj[a-1][b-1] = c;
        adj[b-1][a-1] = c;
    }
    for(int i = 0; i < n; i++)
        adj[i][i] = 0;
    for(int k = 0; k < n; k++)
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
    int v1, v2;
    cin >> v1 >> v2;
    ll ans = min(adj[0][v1-1] + adj[v1-1][v2-1] + adj[v2-1][n-1], adj[0][v2-1] + adj[v2-1][v1-1] + adj[v1-1][n-1]);
    if(ans >= INF) cout << -1;
    else cout << ans;
    return 0;
}

v1, v2 정점을 반드시 거치면서 1번 정점에서 N번 정점으로 최단 경로로 이동하는 경우는 두가지가 있다.

(1 ~ v1) + (v1 ~ v2) + (v2 ~ n)
(1 ~ v2) + (v2 ~ v1) + (v1 ~ n)

( ) : 두 정점 간의 최단 경로

플로이드-와샬 알고리즘으로 각 정점간의 최단 경로를 구할 경우 n 이 최대 800, 약 5억으로 1초안에 계산할 수 있다.

두 최단 경로 중 길이가 짧은 값을 정답으로 출력 한다. 하지만 이동 경로가 없는 경우에는 정답이 INF 이상의 값을 가지게 되므로 -1 을 출력해 주어야 한다.

특정 테스트 케이스에서는 정답의 후보가 3e9 까지 계산되어 int 형의 범위를 초과할 수 있다. long long 자료형을 사용해주어야 산술 오버플로가 발생하지 않는다.