题目大意
给出一张图，请输出其中任意一条可行的从点 11 到点 nn 的最短路径。
输入输出格式
输入格式
第一行：两个整数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 nn . Your task is to find the shortest path between the vertex 11 and the vertex nn .
输入格式：
The first line contains two integers nn and mm ( 2<=n<=10^{5},0<=m<=10^{5}2<=n<=105,0<=m<=105 ), where nn is the number of vertices and mm is the number of edges. Following mm lines contain one edge each in form a_{i}ai , b_{i}bi and w_{i}wi ( 1<=a_{i},b_{i}<=n,1<=w_{i}<=10^{6}1<=ai,bi<=n,1<=wi<=106 ), where a_{i},b_{i}ai,bi are edge endpoints and 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
分析：模板提
#include <bits/stdc++.h> using namespace std; #define ll long long const int N=200005; int n,m,st,en; bool vis[N];//标记数组 ll dist[N];//距离数组 int pre[N];//前驱 int head[N],tot; //结构体数组edge存边，edge[i]表示第i条边, //head[i]存以i为起点的第一条边(在edge中的下标) struct node { int next; //下一条边的存储下标 int to; //这条边的终点 ll w;//权值 } edge[N*4]; ///tot为边的计数，从0开始计，每次新加的边作为第一条边，最后倒序遍历 void add(int u,int v,ll w) { edge[tot].to=v; edge[tot].w=w; edge[tot].next=head[u]; head[u]=tot++; } void init() { tot=0; memset(head,-1,sizeof(head)); memset(pre,-1,sizeof(pre)); } struct Rec { int id; //节点编号 ll dis; //距离 /*bool operator<(const Rec &tmp)const{ return dis>tmp.dis; } */ }; bool operator <(const Rec&a,const Rec&b) { return a.dis>b.dis; } priority_queue<Rec> q;//重载小于号实现小根堆 void dijkstra() { for(int i=0; i<=n; i++) dist[i]=1e18; memset(vis,0,sizeof(vis)); dist[st]=0; Rec rec;rec.id=st;rec.dis=0; q.push(rec); while(!q.empty()) { int u=q.top().id; q.pop(); if(vis[u]) continue; vis[u]=1; for(int i=head[u]; i!=-1; i=edge[i].next) //遍历以u为起点的所有边,与输入顺序相反 { int v=edge[i].to; ll w=edge[i].w; if(dist[v]>dist[u]+w) { dist[v]=dist[u]+w; Rec rec; rec.id=v; rec.dis=dist[v]; q.push(rec); pre[v]=u; } } } } vector<int> path; void getPath() { for(int i=en; i!=-1; i=pre[i]) { path.push_back(i); } } int main() { scanf("%d%d",&n,&m); st=1;en=n; int u,v; ll w; init(); for(int i=1; i<=m; i++) { scanf("%d%d%lld",&u,&v,&w); add(u,v,w); add(v,u,w); } dijkstra(); if(dist[en]==1e18) { cout<<"-1"<<endl; } else { //cout<<dist[en]<<endl; getPath(); for(int i=path.size()-1;i>=0;i--) { cout<<path[i]<<" "; } cout<<endl; } return 0; }
