알고스팟 - ROUTING

https://algospot.com/judge/problem/read/ROUTING

노이즈의 증폭이 최소가 되는 경로를 찾는 문제이다. 책에는 "노이즈 $c$ 는 언제나 1 이상 3 이하의 실수입니다" 라고 나와있다고 한다.

음.. 이게 딱히 문제는 없을 거 같지만, $c$의 범위를 몰라서 정답의 범위를 모르기때문에, 무한대값(INF)를 설정을 못한다. INF=987654321 로 설정하면 오답이 나온다.
987654321 보다 큰 경로만 남아있을 때, 방문하지 않은 정점들은 987654321 일테니 탐색하지 않아버린다.

근데 모든 노이즈가 3이면 어떻게 될까. 3^10000 ...!!

방문한 노드와 방문하지 않은 노드를 따로 구분해야한다. 다익스트라에서는 음수인 가중치가 없을테니 방문하지 않은 노드를 -1 로 해도 될거같다.

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

typedef long long lld;
struct edge {
    int next;
    double weight;
    bool operator < (const edge& p) const {
        if(abs(weight - p.weight) < 1e-9) return next < p.next;
        return weight > p.weight;
    }
};
vector<edge> adj[10001];
bool visited[10001];

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        int n, m;
        scanf("%d %d", &n, &m);
        for(int i=0; i<n; ++i){
            adj[i].clear();
            visited[i] = false;
        }
        while(m--){
            int u, v;
            double w;
            scanf("%d %d %lf", &u, &v, &w);
            adj[u].push_back({v, w});
            adj[v].push_back({u, w});
        }
       
        double cost[10001]={};
        priority_queue<edge> pq;
        pq.push({0, 1});
        cost[0] = 1;
        visited[0] = true;
        while(!pq.empty()){
            int cur = pq.top().next;
            double curW = pq.top().weight;
            pq.pop();
           
            if(cur == n-1) break;
           
            for(int i=0; i<adj[cur].size(); ++i){
                int next = adj[cur][i].next;
                double nextW = cost[cur] * adj[cur][i].weight;
                if(!visited[next] || cost[next] > nextW){
                    visited[next] = true;
                    cost[next] = nextW;
                    pq.push({next, nextW});
                }
            }
        }
       
        printf("%lf\n", cost[n-1]);
    }
    return 0;
}