ROUTING
4227 ワード
(ソース)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;
}
Reference
この問題について(ROUTING), 我々は、より多くの情報をここで見つけました https://velog.io/@dlsghl92/ROUTING신호라우팅テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol