[알고스팟][C++] ROUTING: 신호 라우팅

문제 링크: https://algospot.com/judge/problem/read/ROUTING

 

다익스트라 알고리즘을 적당히 변형해주면 됩니다. 모든 간선의 가중치가 1 이상이기 때문에 어떤 간선을 지났을 때 경로가 짧아지지 않아 다익스트라 알고리즘을 사용할 수 있습니다.

시작값이 1이고 cost를 더하는 것이 아닌 곱해주는 것으로만 바꿔주면 됩니다.

#pragma GCC optimize ("Ofast")

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


int n, m;
const int MAX_V = 10000;
vector<pair<int, double>> adj[MAX_V];	// idx, cost

vector<double> dijkstra_mul(int src) {
	vector<double> dist(n, numeric_limits<double>::max());
	dist[src] = 1.0;
	priority_queue<pair<double, int>> pq;	// cost(-), idx
	pq.emplace(-1.0, src);

	while (!pq.empty()) {
		double cost = -pq.top().first;
		int here = pq.top().second;
		pq.pop();

		// 지금 꺼낸것보다 더 짧은 경로가 있는 경우
		if (dist[here] < cost) continue;

		// 인접한 노드 검사
		for (auto& edge : adj[here]) {
			int there = edge.first;
			double nextDist = cost * edge.second;

			// 더 짧은 경로 발견
			if (dist[there] > nextDist) {
				dist[there] = nextDist;
				pq.emplace(-nextDist, there);
			}
		}
	}
	return dist;
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int t;
	cin >> t;
	while (t--) {
		cin >> n >> m;

		for (int i = 0; i < n; ++i)
			adj[i].clear();

		int a, b;
		double c;
		for (int i = 0; i < m; ++i) {
			cin >> a >> b >> c;
			adj[a].emplace_back(b, c);
			adj[b].emplace_back(a, c);
		}

		auto dist = dijkstra_mul(0);
		cout << setprecision(10) << fixed << dist[n - 1] << '\n';
	}

	return 0;
}