题目大意

UVA1599 Ideal Path

Mosklia @ 2018-05-11 17:49:31

题目描述来源：《算法竞赛入门经典第二版》刘汝佳著

理想路径（Ideal Path, NEERC 2010, UVa1599）

题目描述：

给定一个n个点m条边的无向图，每条边上都涂有1种颜色。求点1到点n的一条路径，使得经过的边数最少，在此前提下，经过边的颜色序列最小。可能有自环与重边。输入保证至少存在一条连接1和n的道路。

输入格式：

输入共m+1行：

第一行2个空格整数：n和m。

以后m行，每行空格隔开的3个整数a_i,b_i,c_i，表示在a_i,b_i之间有一条颜色为c_i的道路。

输出格式

输出共两行：

第一行1个正整数k，表示1到n至少需要经过k条边。

第二行包含k个空格隔开的正整数，表示从1到n依次经过的边的颜色。

输入输出样例：

输入样例：

输出样例：

2
1 3

输入输出样例解释：

路径依次如下：

$3\rightarrow4$，颜色为$3$。 ## 数据范围： $2\leq n \leq 10^5, 1 \leq m \leq 2 \times 10^5,1\leq c_i \leq 10^9$。对于任意$i \in [1,m]$有$1 \leq a_i,b_i \leq n$。

by Mosklia @ 2018-05-11 17:56:17

注：对于两个长度为k的序列a,b，当存在i \in [1,k]使a_i < b_i，且对于任意j \in [1,i)都有a_j = b_j时，a<b。

原文：A sequence (a1, a2, . . . , ak) is lexicographically smaller than a sequence (b1, b2, . . . , bk) if there exists i such that ai < bi , and aj = bj for all j < i.

by 一扶苏一 @ 2018-06-20 21:26:52

@ yjjr

by 一扶苏一 @ 2018-06-20 21:27:12

@yjjr

by yjjr @ 2018-06-22 23:21:38

@Sparky_14145 感谢您的贡献！