题目

Background

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。 请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n号点，则输出 −1。

Input

第一行包含整数 n 和 m。 接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

Output

输出一个整数，表示 1号点到 n 号点的最短距离。 如果路径不存在，则输出 −1。

Limitation

1≤𝑛,𝑚≤1.5×10^5 1≤n,m≤1.5×10^5

思路

数据结构

从数据范围 可以看出输入的图是稠密图,用邻接矩阵肯定是不行的,但我们可以使用邻接表。

算法

直接暴力每一种方法一定会超时，所以我们可以使用Dijkstra来实现。

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,z,idx;
//h是邻接表数组:存储头节点
//c数组:存储边的目标节点
//ne数组:存储下一个节点
//d数组:存储边长
//dist数组:存储最短距离
int h[150001],c[300002],ne[300002],d[150001],dist[150001];
bool vis[150001];
//vis数组:标记
//向邻接表中添加边
void wsd(int x,int y,int z){
    c[idx]=y;
    d[idx]=z;
    ne[idx]=h[x];
    h[x]=idx++;
    return;
}
int Dijkstra_plus(){
    //优先队列q:存储节点及其与起点的距离
    //first:距离,second:节点编号
    priority_queue<pair<int,int>>q;
    //初始化
    memset(dist,0x3f,sizeof dist);
    //起点到自身的距离为0
    dist[1]=0;
    //将起点及其距离加入优先队列
    q.push({0,1});
    while(!q.empty()){
        //取当前距离起点最近的节点及其距离
        pair<int,int>p=q.top();
        q.pop();
        //如果访问过,就跳过
        if(vis[p.second]){
            continue;
        }
        //标记该节点为已访问
        vis[p.second]=1;
        //遍历当前节点的所有邻接边
        for(int i=h[p.second];i!=-1;i=ne[i]){
            //如果通过当前节点到达邻接节点的距离更短(可以优化)
            if(dist[c[i]]>dist[p.second]+d[i]){
                //更新邻接节点到起点的最短距离
                dist[c[i]]=dist[p.second]+d[i];
                //将相连节点及其新的取负距离(取负是为了实现小根堆)加入
                q.push({-dist[c[i]],c[i]});
            }
        }
    }
    //如果终点n的距离仍为极大值,说明无法到达,返回-1
    if(dist[n]==0x3f3f3f3f){
        return -1;
    }
    //返回从起点到终点n的最短距离
    return dist[n];
}
int main(){
    cin>>n>>m;
    //初始化邻接表
    memset(h,-1,sizeof h);
    //读入每条边的信息,并添加到邻接表中
    for(int i=1;i<=m;i++){
        cin>>x>>y>>z;
        wsd(x,y,z);
    }
    cout<<Dijkstra_plus();
    return 0;
}