백준 - 1504

문제

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

1504번: 특정한 최단 경로

1 → u → v → N (혹은 1 → v → u → N)의 최단 경로의 길이를 찾는 문제였다.

 

문제 풀이

플루이드 워셜 알고리즘을 이용해 풀었다. 처음에 1 → u → v → N 경우에 대해서만 최솟값을 찾아줘서 틀렸는데 1 → v → u → N 경우와도 비교해 최솟값을 구해서 맞췄다. MAX_INT 값은 간선의 최대 길이인 1000 * 간선의 최대 개수인 200000을 해준 200000000보다 큰 값으로 정해줬다.

 

MAX_INT 값을 3번 더해도 6억이라 int 범위를 넘어서지 않아서 long long 대신 int로 선언해도 문제는 없을 것 같다.

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include<iostream>

using namespace std;

#define MAX_INT 300000000

long long map[801][801]; 

int main()
{
    int N, E;
    int i, j, k;
    int a, b, c;
    int u, v;
    long long minDist;

    scanf("%d %d", &N, &E);

    for (i = 0; i <= N; i++) {
        for (j = 0; j <= N; j++) {
            if (i == j) {
                map[i][j] = 0;
                continue;
            }
            map[i][j] = MAX_INT;
        }
    }

    for (i = 0; i < E; i++) {
        scanf("%d %d %d", &a, &b, &c);
        map[a][b] = c;
        map[b][a] = c;
    }
    
    scanf("%d %d", &u, &v);

    for (k = 1; k <= N; k++) {
        for (i = 1; i <= N; i++) {
            for (j = 1; j <= N; j++) {
                map[i][j] = min(map[i][k] + map[k][j], map[i][j]);
            }
        }
    }

    minDist = map[1][u] + map[u][v] + map[v][N];
    minDist = min(minDist, map[1][v] + map[v][u] + map[u][N]);

    if (minDist >= MAX_INT) printf("-1");    
    else printf("%.lld", minDist);

    return 0;
}

/*
4 3
1 2 2
1 3 1
2 4 3
1 3

7
*/