ROUTING

AOJ ROUTING

다익스트라

src = 0; sink = n-1인 최소비용을 구해 출력을 한다.
여기서 비용은 각 정점을 이동하는데 드는 비용의 합이 아니라 곱이다.
오버플로를 방지하기 위해서 log를 사용하고 마지막에 exp연산을 통해 원래의
값을 출력한다.

[-] Collapse

#include<cstdio>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
int n, c;
vector<vector<pair<int, double> > > adj;
void dijkstra(int src){
    vector<double> dist(n, 987654321);
    dist[src] = 0;
    priority_queue<pair<double, int> > pq;
    pq.push(make_pair(0, src));
    while (!pq.empty()) {
        double cost = -pq.top().first;
        int here = pq.top().second;
        pq.pop();
        if (dist[here] < cost) continue;
        for (int i = 0; i < adj[here].size(); i++){
            int there = adj[here][i].first;
            double nextDist = cost + adj[here][i].second;
            if (dist[there] > nextDist) {
                dist[there] = nextDist;
                pq.push(make_pair(-nextDist, there));
            }
        }
    }
    printf("%.10lf\n", exp(dist[n - 1]));
    return;
}
int main(){
    int t; scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &c);
        adj = vector<vector<pair<int, double> > >(n);
        for (int i = 0; i < c; i++) {
            int src, sink; double dist; scanf("%d%d%lf", &src, &sink, &dist);
            adj[src].push_back(make_pair(sink, log(dist)));
            adj[sink].push_back(make_pair(src, log(dist)));
        }
        dijkstra(0);
    }
}