[[problem:ROUTING]]
[[연습 문제|problem:ROUTING]]
라우팅 문제를 푸는데, 오답으로 처리가 됩니다.
혹시 어떤부분에서 오답처리가 되는지 도움을 주실 수 있으신가요 ?

자료구조 : vector를 이용하여 인접리스트를 만들었습니다.

알고리즘 : vector로 만든 인접리스트를 기반으로
DFS를 수행합니다.
A노드에서 B노드로 갈 때, 가중치만큼 값이 곱해집니다.
그리고 해당 값은 stack에 저장합니다.
B가 더이상 유망하지 않다면 해당 값은 pop해줍니다.
최초로 목적지까지 도착했을 때 값을 MIN으로 놔두고
길목을 탐색할때마다 MIN보다 커질거 같으면 유망하지
않다고 판단하고 탐색하지 않습니다. 이렇게 최종적으로
가장 작은 값만 갖고있게되고, 해당 값을 출력해줍니다.

무엇이 문제인지 도와주시면 감사하겠습니다 !

#include <stdio.h>
#include <iostream>
#include <stack>
#include <vector>
#include <stdlib.h>

using namespace std;

int N; // 노드 수
int vertex; //간선의 수

int visit[10001] = { 0, };
long double res = 1; // 결과값
long double MIN_res = 1.7976931348623158e+308;
vector<long double> arr[10001];
stack<long double> s;
stack<long double> s_val;  //값 비교용 stack


/// 인접리스트 생성

/// 추가사항: 양방향 그래프 될 수 있도록 해주고, (  O ) 
///           자료형 double로 바꿔준다. ( O )

void input() {
    int node_a;
    int node_b;
    long double val;
    for (int i = 0; i < vertex; i++) {
        cin >> node_a >> node_b >> val;
        arr[node_a].push_back(node_b);
        arr[node_b].push_back(node_a);
        arr[node_a].push_back(val);
        arr[node_b].push_back(val);
    }

}

void DFS(int start) {

    if (start == N - 1) {  // 마지막노드에 도착하였다면.
        MIN_res = s_val.top();  //마지막노드까지 왔다는 것은, 최소의 값이라는 것을 의미하므로. 
        s_val.pop();
        return;
    }

    //들어오는 값 스택에 넣어주고
    s.push(start);

    // visit 해준다.
    visit[start] = 1;
    
    int temp_node = 0;

    for (int i = 0; i < arr[start].size(); i += 2) {

        temp_node = arr[start][i];  // 다음으로 갈 노드 

        if (!visit[temp_node] && (s_val.top()*arr[start][i+1])<MIN_res ) {  // 방문하지 않았고, 방문하지 않았다 하더라도 곱했을 경우 최소증폭보다 값이 크다면 X
            res = s_val.top()*arr[start][i + 1];
            s_val.push(res);
            DFS(temp_node);
        }
    }


    // 더이상 갈 곳이 없을때에는 pop해주려는 부분에 대해 visit 초기화 시켜주고, pop해준다.
    int temp = 0;
    temp = s.top();
    visit[temp] = 0;  
    s.pop();
    s_val.pop();
    


}


/// 초기화 함수
void init() {

    MIN_res = 1000000;
    for (int i = 0; i < N; i++) {
        visit[i] = 0;
    }

    // vector에서 사용한 동적메모리 해제
    for (int i = 0; i < N; i++) {
        arr[i].clear();
    }
}

void Test();
int main() {
    

    /// TestCase 입력
    int TestCase = 0;
    //freopen("in.txt", "r", stdin);
    cin >> TestCase;
    for (int i = 0; i < TestCase; i++) {

        /// 노드 수 입력
        cin >> N;

        /// 간선의 수 입력
        cin >> vertex;


        /// 간선정보 입력
        input();

        // Start : 0  , End : N-1 번
        /// DFS 
        s_val.push(1);  // 처음에 value 1 넣어주고 시작.
        DFS(0);

        cout.setf(ios::fixed);
        cout.precision(10);
        cout << MIN_res<<endl;
        init();
    }
    return 0;
}

/// Just Test
void Test() {


    // 인접리스트 출력
    for (int i = 0; i < vertex; i++) {
        cout << "시작:" << i << " ";
        for (int j = 0; j < arr[i].size(); j += 2) {
            cout << " 정점:" << arr[i][j] << " " << " 값:" << arr[i][j + 1] <<"/";
        }
        cout << endl;
    }
}
</spoiler>