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

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

 

문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1)

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

 

접근방식

디엑스트라 알고리즘을 응용하는 문제였다.
1번과 n번사이 최단경로 중에 두 정점 v1, v2를 들려야 한다는 조건이 붙는다.
여기서 그러한 경로가 없다면 -1을 출력하라는 조건이 뭔가 걸렸다. 생각해 보니 그러한 경로가 없는 것은 그래프가 단절되어서 아예 연결이 안된 경우를 의미하는 것이었다.

두 정점을 들리는 조건을 만족하는 경우는 2가지다
1 -> v1 -> v2 -> n
1 -> v2 -> v1 -> n
이 두가지 경우 중에 더 작은 값이 최종 답이 된다.

그럼 그래프가 단절된 경우를 어떻게 구별하나?
디엑스트라를 수행시에 도착해야 하는 정점에 도착하면 그 정점의 dist값을 반환하도록 했다.
여기서 걸리지 않고 while을 빠져나오는 경우는 도착 정점을 발견하지 못한, 즉 그래프가 끊어졌다고 판단하고 bool 변수로 체크해준다.
그리고 결과 출력시에 bool 변수를 고려한다.
false 라면 최단경로 탐색 불가능 -> -1
true 라면 최단경로 탐색 완료 -> result
를 출력한다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#define VMAX 801
#define INF 2100000000

using namespace std;

vector<pair<int,int>> a[VMAX];
bool pass = true;

int dijkstras(int start, int end){
  priority_queue<pair<int,int>> pq;
  int dist[VMAX];
  for(int i=1; i<VMAX; i++) 
    dist[i] = INF;
  dist[start]=0;
  pq.push({-0, start});
  while(!pq.empty()){
    int x = pq.top().second;
    int wx = -pq.top().first;
    pq.pop();
    if(x==end) return wx;

    for(int i=0; i<a[x].size(); i++){
      int y = a[x][i].first;
      int wy = a[x][i].second;
      if(dist[y] > dist[x] + wy){
        dist[y] = dist[x] + wy;
        pq.push({-dist[y], y});
      }
    }
  }
  pass = false;
  return 0;
}

int main(){
  int n,e; cin >> n >> e;
  int v1, v2;
  for(int x,y,w,i=0; i<e; i++){
    scanf("%d %d %d", &x, &y, &w);
    a[x].push_back({y,w});
    a[y].push_back({x,w});
  }
  cin >> v1 >> v2;
  int num1 = dijkstras(1, v1) + dijkstras(v1, v2) + dijkstras(v2, n);
  int num2 = dijkstras(1, v2) + dijkstras(v2, v1) + dijkstras(v1, n);
  int result = min(num1, num2);
  if(pass)
    printf("%d\n", result);
  else
    printf("-1\n");
}

 

 

개선할 수 있는 사항들

1. 디엑스트라 수행 횟수를 줄일 수 있다. 현재 6번 수행중이다.
개선하게 된다면
1) 1->v1, 1->v2 경로 구하기
2) v1-> v2 경로 구하기
3) n->v1, n->v2 경로 구하기
이렇게 3번의 디엑스트라를 통해 해를 찾을 수 있다.

2. 디엑스트라 중간에 최단경로를 찾는 것이 불가능하다고 판단될 경우 바로 프로그램을 종료시켜 시간을 아낄 수 있다.