[그래프] ROUTING 신호 라우팅

1. 다익스트라 문제

 

이 문제는 간단한 다익스트라 문제이다.

 

이 문제의 핵심은 정수의 거리가 아닌 

 

실수인 노이즈의 증폭도라는 것이다.

 

 

따라서 간선을 지나가면서 가중치를 더하는게 아니라 곱을 하는 것이다.

 

 

2. 책의 풀이

 

책에서는 곱을 로그의 합으로 변환해서 문제를 해결하였다.

 

로그의 합의 최소를 구하고 exp()만 해주면 답을 구할 수 있다. 

 

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <iomanip>
 
using namespace std;
 
 
int C;
int N, M;
 
vector<vector<pair<double, int> > > circuit;
 
double dijkstra()
{
    vector<double> ret(N, 5.0/0.0);
    priority_queue<pair<double, int> , vector<pair<double, int> >, greater<pair<double, int> > > pq;
    ret[0] = 1.0;
    pq.push(make_pair(1.0, 0));
    while(!pq.empty())
    {
        double cost = pq.top().first;
        int here = pq.top().second;
        pq.pop();
 
        if(ret[here] < cost) continue;
 
        for(int i = 0; i < circuit[here].size(); i++)
        {
            int there = circuit[here][i].second;
            double nextDist = cost * circuit[here][i].first;
            if(nextDist  < ret[there] )
            {
                ret[there] = nextDist;
                pq.push(pair<double, int>(nextDist, there));
            }
        }
    }
    return ret[N-1];
}
 
 
int main()
{
    cin>>C;
    while(C--)
    {
 
        cin>>N>>M;
        circuit = vector<vector<pair<double, int> > >(N);
        for(int i = 0; i < M; i++)
        {
            int a, b;
            double c;
            cin>>a>>b>>c;
            circuit[a].push_back(make_pair(c, b));
            circuit[b].push_back(make_pair(c, a));
        }
        cout<<fixed<<setprecision(10);
        cout<<dijkstra()<<"\n";
 
    }
}

ROUTING