반응형
https://www.acmicpc.net/problem/1504
문제 해결 알고리즘
v_1에서 시작하는 다익스트라와 v_2에서 시작하는 다익스트라를 구해준 후에 양방향 그래프라는 점을 이용해서
1에서 $v_1$으로 가는 최단 경로 + $v_1$에서 $v_2$로 가는 최단 경로 + $v_2$에서 N으로 가는 최단 경로
1에서 $v_2$으로 가는 최단 경로 + $v_2$에서 $v_1$으로 가는 최단 경로 + $v_1$에서 N으로 가는 최단 경로
를 구해준다.
그 중 적은 수를 출력해준다. 이 때 그 값이 INF값보다 크다면 경로가 없다는 것이므로 -1을 출력한다.
(INF값은 1e9가 넘어가면 92퍼에서 틀린다.)
아래의 링크에 다익스트라 알고리즘이 설명되어있다.
https://kimmessi.tistory.com/185?category=871925
소스 코드
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e7;
vector<pair<int, int>> graph[810];
int d[2][810];
int N, E;
int v_1, v_2;
int result1 = 0, result2 = 0;
void dijkstra(int start_node, int n){
d[n][start_node] = 0;
priority_queue<pair<int, int>> pq;
pq.push({0, start_node});
while(!pq.empty()){
int dist = -pq.top().first;
int now = pq.top().second;
pq.pop();
if(d[n][now] < dist) continue;
for(int i=0;i<graph[now].size();i++){
int cost = dist + graph[now][i].second;
if(cost < d[n][graph[now][i].first]){
d[n][graph[now][i].first] = cost;
pq.push({-cost, graph[now][i].first});
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> E;
for(int i=0;i<E;i++){
int a, b, c; cin >> a >> b >> c;
graph[a].push_back({b, c});
graph[b].push_back({a, c});
}
cin >> v_1 >> v_2;
fill(&d[0][0], &d[1][802], INF);
dijkstra(v_1, 0);
dijkstra(v_2, 1);
result1 = d[0][1] + d[0][v_2] + d[1][N];
result2 = d[1][1] + d[1][v_1] + d[0][N];
int result = min(result1, result2);
if(result >= INF) cout << -1;
else cout << result;
}
반응형
'알고리즘 문제 해결 > BOJ' 카테고리의 다른 글
[다익스트라] BOJ 1916 최소비용 구하기 (C++) (0) | 2022.05.20 |
---|---|
[MST] BOJ 4386 별자리 만들기 (0) | 2022.05.17 |
[DP] BOJ 2293 동전 1 (C++) (0) | 2022.05.13 |
[DP] BOJ 2011 암호코드 (C++) (0) | 2022.05.10 |
[DP] BOJ 1890 점프 (C++) (0) | 2022.05.07 |