644 人解决，680 人已尝试。
809 份提交通过，共有 1646 份提交。
0.8 EMB 奖励。
3073. 道路排序
单点时限: 2.0 sec
内存限制: 256 MB
平面上有 $N$ 个结点，结点编号为 $1,2,3,\cdots ,N$。
这 $N$ 个结点中有 $M$ 条道路。每条道路采用如下格式表示：$(i,j,a_{ij})，i\neq j$，即：结点 $i$ 与结点 $j$ 之间有一条道路，道路长为 $a_{ij}$。
注意：任意两个结点之间最多只有一条道路。
图中，结点 $1$ 和结点 $7$ 之间有一条道路，道路长为 $30$，结点 $1$ 与结点 $2$ 之间有一条道路，道路长为 $28$。
请将这 $M$ 条道路按照长度递减排序；如果道路长度相等，则按照道路的第一个结点编号 $i$ 递增排序；如果第一个结点编号 $i$ 相同，则按照第二个结点编号 $j$ 递增排序。
输入格式
第 1 行：整数 $T$ ($1 \le T \le 10$) 为问题数。
对于每个问题，按如下格式输入：
第 1 行：输入两个正整数 $N$，$M$，($2 \le N \le 200，1 \le M \le \frac{N\times (N-1)}{2}$)，$N$ 表示结点的个数，$M$ 表示道路数。
接下来 $M$ 行，每行输入三个正整数 $i，j，a_{ij}$，($1\le i\le N，1\le j\le N,i\neq j, 1≤a_{ij}≤500$)，表示结点 $i$ 到结点 $j$ 之间有一条道路，道路长度为 $a_{ij}$，数之间由一个空格分隔。
输出格式
对于每个问题，输出一行问题的编号（0 开始编号，格式：case #0: 等）。
接下输出排序后的 M 条道路。每行输出一条道路。具体格式见 SampleOutput。
样例
Input
3 10 12 1 7 30 1 2 28 2 4 20 2 5 10 2 3 10 3 10 10 7 5 20 5 10 70 8 5 20 8 6 40 7 6 35 6 9 10 2 1 1 2 30 4 6 1 3 30 2 3 19 1 2 30 1 4 19 2 4 50 4 3 30
Output
case #0: (5,10,70) (8,6,40) (7,6,35) (1,7,30) (1,2,28) (2,4,20) (7,5,20) (8,5,20) (2,3,10) (2,5,10) (3,10,10) (6,9,10) case #1: (1,2,30) case #2: (2,4,50) (1,2,30) (1,3,30) (4,3,30) (1,4,19) (2,3,19)
创建: 9 年，5 月前.
修改: 6 年，2 月前.
最后提交: 1 月，4 周前.
来源: N/A
题目标签