题意翻译
题目大意
给出一张图, 请输出其中任意一条可行的从点 111 到点 nnn 的最短路径.
输入输出格式
输入格式
第一行: 两个整数 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 n n . Your task is to find the shortest path between the vertex 1 1 1 and the vertex n n n .
输入格式
The first line contains two integers n n n and m m m ( 2<=n<=105,0<=m<=105 2<=n<=10^{5},0<=m<=10^{5} 2<=n<=105,0<=m<=105 ), where n n n is the number of vertices and m m m is the number of edges. Following m m m lines contain one edge each in form ai a_{i} ai , bi b_{i} bi and wi w_{i} wi ( 1<=ai,bi<=n,1<=wi<=106 1<=a_{i},b_{i}<=n,1<=w_{i}<=10^{6} 1<=ai,bi<=n,1<=wi<=106 ), where ai,bi a_{i},b_{i} ai,bi are edge endpoints and wi w_{i} wi 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
题解
最短路模板题...
在计算最短路过程中, pre[i] 记录点 i 的最短路前驱.
利用 pre[i] 数组输出答案即可.
注意最后一个点范围爆 long long.
- code:
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <queue>
- #include <cstring>
- using namespace std;
- typedef long long LL;
- const int N = 2e5 + 5;
- int n, m;
- struct edge { int to, nxt, val; } e[N];
- int cnt, head[N];
- void add(int from, int to, int val) {
- e[++ cnt].to = to;
- e[cnt].val = val;
- e[cnt].nxt = head[from];
- head[from] = cnt;
- }
- int dis[N], vis[N], pre[N];
- LL ans[N];
- void spfa() {
- for(int i = 1;i <= n;i ++) dis[i] = 1e15;
- queue <int> q; q.push(1);
- dis[1] = 0; vis[1] = 1;
- while(! q.empty()) {
- int tp = q.front(); q.pop();
- vis[tp] = 0;
- for(int i = head[tp]; i ;i = e[i].nxt) {
- int to = e[i].to, val = e[i].val;
- if(dis[to]> dis[tp] + val) {
- dis[to] = dis[tp] + val;
- pre[to] = tp;
- if(! vis[to]) q.push(to), vis[to] = 1;
- }
- }
- }
- }
- signed main() {
- cin>> n>> m;
- for(int i = 1, a, b, l;i <= m;i ++) {
- cin>> a>> b>> l;
- add(a, b, l); add(b, a, l);
- }
- spfa();
- if(dis[n] == 1e15) { cout << "-1"; return 0; }
- int t = n, tot = 0;
- while(t != 1) {
- ans[++ tot] = t;
- t = pre[t];
- }
- ans[++ tot] = 1;
- for(int i = tot; i ;i --) cout << ans[i] << " ";
- return 0;
- }
就这样, 我又水了一篇题解.
来源: http://www.bubuko.com/infodetail-3152720.html