#P1268. Shortest path / 边权递增最短路
Shortest path / 边权递增最短路
题目描述
王国共有 个城市(以 、、、 为标记)和 条双向道路。任何两个城市之间可能有几条道路,但没有任何道路连接同一个城市(没有环)。
你的任务是找到从城市 到城市 的最短路径,你经过的边的长度必须严格按照递增的顺序排列。
【简要题意】
给出一张 个点, 条边的有向带权图,要求找一条从 到 且边权严格递增的最短路。
.
输入格式
第一行中有一个整数 (),表示总共有 个测试用例。
对于每个测试用例,有两个整数 ()和 (),它们具有与上述相同的含义。
然后有 条线,每条线中有三个整数 ()、()。
最多有十个测试用例满足 或 。
输出格式
对于每个测试用例,您应该输出在上述任务中找到的最短路径的长度。 如果不存在这样的路径,您应该只输出No answer
。
样例输入输出
4
4 6
1 2 1
1 2 2
2 3 3
2 3 1
3 4 2
4 3 6
3 2
1 2 1
2 3 1
3 1
1 2 1
2 2
2 1 1
1 2 2
10
No answer
No answer
1