백준 1504번 : 특정한 최단 경로

문제 링크 : https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

 문제 설명 

 

1. 방향 성이 없는(양방향) 그래프가 주어지고 시작점 부터 끝점 까지의 최단거리를 출력.

2. 단, 주어지는 2개의 정점을 방문하여야함.

 

 알고리즘 

 

사람들은 다익스트라로 거의 풀었는데 나는 플루이드-와샬 알고리즘으로 풀었다.

플루이드-와샬 알고리즘이 더쉽지만 다익스트라로 많이 푼이유를 질문게시판에 남겼는데 이런 답변이..그럼 본론으로

 

1. 배열초기화

2. 간선데이터 입력 (양방향으로 입력 )

3. 플루이드 - 와샬 알고리즘으로 최단 거리 갱신.

4. a 와 b중 먼저 방문하는 것이 목적지에 더먼저 도착하는 쪽 최단거리를 출력 

 

 

 코드 

 

#include<iostream>
#include<algorithm>
 
using namespace std;
typedef long long ll;
 
ll INF = 987654321;
ll arr[805][805];
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
 
    
    int N, M;
    cin >> N >> M;
 
    //배열 초기화
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++){
            if (i == j)arr[i][j] = 0;
            else arr[i][j] = INF;
        }
    }
 
    //간선데이터 입력
    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        arr[a][b] = c;
        arr[b][a] = c;
    }
 
    //플루이드 와샬
    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i == j)continue;
                arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
            }
        }
    }
 
 
 
 
    int a, b;
 
    cin >> a >> b;
    //a,b중 먼저 들리는 것이 더 가까운 정점을 이용
    ll result = min(arr[1][a] + arr[a][b] + arr[b][N], arr[1][b] + arr[b][a] + arr[a][N]);
    //최단 거리가 존재 하지 않을경우 -1출력
    if (result >= INF)cout << -1;
    else cout << result;
 
 
            
}