BOJ 1504 특정한 최단 경로

1 개요

BOJ 1504 특정한 최단 경로

• 백준 온라인 저지 1504번 문제
• BOJ 32단계

2 C++

C++

Copy

#include <bits/stdc++.h>
#include <limits.h>
using namespace std;

int N, E;
int A[1001][1001];
int visited[1001];
int v1, v2;
int MAX = INT_MAX/4;

int dijkstra(int start, int end) {
	if (start == end) return 0;
	for (int i=1; i<=N; i++) {
		visited[i] = MAX;
	}
	priority_queue<pair<int, int>> pq;
	pq.push({ 0, start });
	visited[start] = 0;
	int x, nx;
	while (!pq.empty()) {
		x = pq.top().second;
		pq.pop();
		for (int nx=1; nx<=N; nx++) {
			if (visited[nx] > visited[x] + A[x][nx]) {
				visited[nx] = visited[x] + A[x][nx];
				pq.push({ -visited[nx], nx });
			}
		}
	}
	return visited[end];
}

int solve() {
    int sum1 = dijkstra(1,v1) + dijkstra(v1,v2) + dijkstra(v2,N);
	int sum2 = dijkstra(1,v2) + dijkstra(v2,v1) + dijkstra(v1,N);
	int result = min(sum1, sum2);
	if (result >= MAX) return -1;
	return result;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> E;
	for (int i=1; i<=N; i++) {
		for(int j=1; j<=N; j++) {
			A[i][j] = MAX;
		}
    }
	int a, b, c;
	for (int i=0; i<E; i++) {
		cin >> a >> b >> c;
		A[a][b] = c;
		A[b][a] = c;
	}
	cin >> v1 >> v2;
    cout << solve();
}