当前位置: 代码迷 >> 综合 >> CF20C Dijkstra? (堆优化的Dijkstra+输出路径)
  详细解决方案

CF20C Dijkstra? (堆优化的Dijkstra+输出路径)

热度:85   发布时间:2024-01-15 06:35:31.0

题意翻译

题目大意

给出一张图,请输出其中任意一条可行的从点 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;}