ROUTING(신호라우팅)

(출처) https://algospot.com/judge/problem/read/ROUTING

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdlib>

using namespace std;
vector<vector<pair<int, double>>> computer_map;
const double INF = numeric_limits<double>::max();

vector<double> routing(int N) {
	vector<double> noise(N, INF);
	priority_queue<pair<double, int>> p_q;
	noise[0] = 1.0;
	p_q.push(pair<double, int> (-noise[0], 0));
	while (!p_q.empty()) {
		int here = p_q.top().second;
		double cost = -p_q.top().first;
		p_q.pop();
		if (cost < noise[here]) continue;

		for (int i = 0; i < computer_map[here].size(); i++) {
			int there = computer_map[here][i].first;
			double next_cost = cost * computer_map[here][i].second;
			if (next_cost < noise[there]) {
				noise[there] = next_cost;
				p_q.push(pair<double, int> (-next_cost, there));
			}
		}
	}
	return noise;
}

int main() {
	int tc;
	scanf("%d", &tc);

	while (tc--) {
		int N, M;
		scanf("%d %d", &N, &M);
		computer_map = vector<vector<pair<int, double>>> (N);

		for (int i = 0; i < M; i++) {
			int a, b;
			double noise;
			scanf("%d %d %lf", &a, &b, &noise);
			computer_map[a].push_back(pair<int, double>(b, noise));
			computer_map[b].push_back(pair<int, double>(a, noise));
		}

		vector<double> ret = routing(N);
		printf("%.*lf \n" ,10, ret[N-1]);
	}
	return 0;
}