[백준oj] 1504번 특정한 최단 경로

www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

---

 

풀이)

이문제도 일단 모든 정점에서부터 다른 모든정점까지의 최단거리를 구해주는Floyd-warshall 알고리즘을 적용시킨뒤, 

1->v1->v2->N 과 1->v2->v1->N중 더 작은 수를 출력해주면 된다.

 

코드)

#include<iostream>
#include<algorithm>
#define MAX 987654321
using namespace std;
int n, m;
int v1, v2;
int arr[1001][1001];

int main() {
	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] = MAX;
		}
	}
    
	for (int i = 0; i < m; i++) {
		int st, en, v;
		cin >> st >> en >> v;
		arr[st][en] = v;
		arr[en][st] = v;
	}


	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
            	//i->j로가는거리와 i->k->j로 가는 경로중 작은값을 초기화
				if (arr[i][j] > arr[i][k] + arr[k][j]) {
					arr[i][j] = arr[i][k] + arr[k][j];
				}
			}
		}
	}
	cin >> v1 >> v2;

	//가는 길목중 하나라도 초기값MAX(업데이트가 안됨==가지못하는길)이면 -1출력
	if (arr[1][v1] == MAX || arr[v1][v2] == MAX || arr[v2][n] == MAX) {
		cout << -1;
		return 0;
	}
	else if (arr[1][v2] == MAX || arr[v2][v1] == MAX || arr[v1][n] == MAX) {
		cout << -1;
		return 0;
	}

	//1->v1->v2->n 과 1->v2->v1->n중 더 작은값 출력
	if (arr[1][v1] + arr[v1][v2] + arr[v2][n] > arr[1][v2] + arr[v2][v1] + arr[v1][n]) {
		cout << arr[1][v2] + arr[v2][v1] + arr[v1][n];
	}
	else if (arr[1][v1] + arr[v1][v2] + arr[v2][n] < arr[1][v2] + arr[v2][v1] + arr[v1][n]) {
		cout << arr[1][v1] + arr[v1][v2] + arr[v2][n];
	}
	return 0;
}