Dijkstra?
题意翻译
题目大意
给出一张图,请输出其中任意一条可行的从点 $1$ 到点 $n$ 的最短路径。
输入输出格式
输入格式
第一行:两个整数n,m,分别表示点数和边数
接下来m行:每行三个整数u,v,w,表示u和v之间连一条边权为w的双向边。
输出格式
一行:一个可行的路径,如果不存在这种路径输出-1
2<=n<=10^5,0<=m<=10^5
题目描述
You are given a weighted undirected graph. The vertices are enumerated from 1 to $ n $ . Your task is to find the shortest path between the vertex $ 1 $ and the vertex $ n $ .
输入输出格式
输入格式
The first line contains two integers $ n $ and $ m $ ( $ 2<=n<=10^{5},0<=m<=10^{5} $ ), where $ n $ is the number of vertices and $ m $ is the number of edges. Following $ m $ lines contain one edge each in form $ a_{i} $ , $ b_{i} $ and $ w_{i} $ ( $ 1<=a_{i},b_{i}<=n,1<=w_{i}<=10^{6} $ ), where $ a_{i},b_{i} $ are edge endpoints and $ w_{i} $ is the length of the edge.
It is possible that the graph has loops and multiple edges between pair of vertices.
输出格式
Write the only integer -1 in case of no path. Write the shortest path in opposite case. If there are many solutions, print any of them.
输入输出样例
输入样例 #1
5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1
输出样例 #1
1 4 3 5
输入样例 #2
5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1
输出样例 #2
1 4 3 5