[알고리즘 20.1.2] 그래프 - 특정 최단거리

문제

---

무방향 그래프가 주어질 때, 정점 1번에서 정점 N번으로 가는 최단거리를 구하려 하는데, 그 과정에서 두 개의 정점을 반드시 거쳐야 한다. 한 번 방문했던 정점을 또 다시 방문하는 것도 허용하고, 간선도 마찬가지로 여러번 방문하는 것을 허용한다고 할 때, 1번에서 N번으로 가는 “특정한" 최단거리를 출력하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. ( 1 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000 ) 둘째 줄부터 간선의 정보가 주어진다. 각 줄은 두 개의 숫자 a, b, c로 이루어져 있으며, 이는 정점 a와 정점 b가 가중치 c인 간선으로 연결되어 있다는 의미이다. 마지막 줄에는 반드시 거쳐야 하는 두 정점 A, B가 주어진다. ( 1 ≤ a, b, A, B ≤ 1,000, 1 ≤ c ≤ 50,000 )

 

출력

---

1번 정점에서 N번 정점으로 가는 “특정한" 최단거리를 출력한다. 단, “특정한" 최단거리란, 주어진 정점 A와 B를 반드시 방문할 때의 최단거리를 의미한다.

 

예제 입력

4 6

1 2 3

2 3 3

3 4 1

1 3 5

2 4 5

1 4 4

2 3

예제 출력

7

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

//T[i] : 정점 i에 도달하는데 걸리는 최단거리
//(1) T[i] 중 최솟값을 정한다. 단, 지금까지 최솟값으로 뽑히지 않았던 값들 중.
//(2) index로부터 뻗어나간다. T[index] + cost
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
const int MAX = 100005;
 
vector <int> graph[MAX];
vector <int> cost[MAX];
 
int n, m;
 
int table[MAX];
bool check[MAX]; //check[i] = true 라면 i는 최단거리가 확정되었다.
 
void inNode(int node){
    for(int i=0; i<=n; i++){
      table[i] = 987987987;
      check[i] = 0;
    } 
    table[node] = 0;
}
 
void distance(){
  for(int i=0; i<=n; i++){
    // (1) 최솟값을 구한다. 단, 지금까지 최단거리로 확정되지 않았던 노드에 대해서.
    // (2) 그 최솟값을 갖는 노드로부터 뻗어나간다.
    int minValue = 987987987, minIndex = -1;
 
    for(int j=1; j<=n; j++){
      if(!check[j] && minValue > table[j]){
        minValue = table[j];
        minIndex = j;
      }
    }
 
    check[minIndex] = true;
    
    for(int j=0; j<graph[minIndex].size(); j++){
      int node2 = graph[minIndex][j];
      int cost2 = cost[minIndex][j];
      
      if(table[node2] > table[minIndex] + cost2){
        table[node2] = table[minIndex]+cost2;
      }
    }
  }
}
 
int main(){
  cin>>n>>m;
 
  int a,b,c;
  for(int i=1; i<=m; i++){
    cin>>a>>b>>c;
    graph[a].push_back(b);
    graph[b].push_back(a);
    cost[a].push_back(c);
    cost[b].push_back(c);
  }
  
  int node1, node2;
  cin>>node1>>node2;
  
  inNode(1);
  distance();
  
  int sum = 0;
  int flag = 0;
  if(table[node1]>table[node2]){
    sum+= table[node2];
    inNode(node2);
    flag = 1;
  }else{
    sum+= table[node1];
    inNode(node1);
  }
  distance();
  
  if(flag==1){
    sum+= table[node1];
    inNode(node1);
  }else{
    sum+= table[node2];
    inNode(node2);
  }
  distance();
  
  sum += table[n];
 
 
  printf("%d\n", sum);
  return 0;
}
 
//예제입력
/*
8 11 0 6
0 1 3
0 5 1
1 2 4
1 3 1
1 5 1
2 4 6
2 6 9
2 7 4
3 4 2
4 6 9
6 7 3
*/