013.md

013 - Passing (★5)

解答

#include <iostream>
#include <vector>
#include <utility> // std::pair
#include <queue> // std::priority_queue
#include <functional> // std::greater

// 辺の情報
struct Edge
{
	// 行先
	int to;

	// コスト
	int cost;
};
const long long INF = (1LL << 60);

// { 距離, 頂点 }
using Pair = std::pair<long long, int>;

// ダイクストラ法
void Dijkstra(const std::vector<std::vector<Edge>>& graph, int startIndex, std::vector<long long>& distances)
{
	// 「現時点での最短距離, 頂点」の順に取り出す priority_queue
	// デフォルトの priority_queue は降順に取り出すため std::greater を使う
	std::priority_queue<Pair, std::vector<Pair>, std::greater<Pair>> pq;
	pq.emplace((distances[startIndex] = 0), startIndex);

	while (!pq.empty())
	{
		const auto[distance, from] = pq.top(); pq.pop();

		// 最短距離でなければ処理しない
		if (distances[from] < distance)
		{
			continue;
		}

		// 現在の頂点からの各辺について
		for (const auto& edge : graph[from])
		{
			// to までの新しい距離
			const long long d = (distances[from] + edge.cost);

			// d が現在の記録より小さければ更新 & pq に追加
			if (d < distances[edge.to])
			{		
				pq.emplace((distances[edge.to] = d), edge.to);
			}
		}
	}
}

int main()
{
	// N 個の街, M 本の道路
	int N, M;
	std::cin >> N >> M;

	// N 頂点のグラフ
	std::vector<std::vector<Edge>> graph(N);
	for (int i = 0; i < M; ++i)
	{
		int A, B, C;
		std::cin >> A >> B >> C;
		--A; --B;
		graph[A].push_back({ B, C });
		graph[B].push_back({ A, C });
	}

	// 街[0] から各街への最短距離
	std::vector<long long> distancesFrom1(N, INF);
	Dijkstra(graph, 0, distancesFrom1);

	// 街[N-1] から各街への最短距離
	std::vector<long long> distancesFromN(N, INF);
	Dijkstra(graph, (N - 1), distancesFromN);

	// 街[i] を経由して街[N-1] まで移動するときにかかる時間の最小値
	for (int i = 0; i < N; ++i)
	{
		std::cout << (distancesFrom1[i] + distancesFromN[i]) << '\n';
	}
}