题目描述

给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为非负值。

请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。

输入

第一行包含整数n和m。

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

数据范围

1≤n,m≤1.5×10^5

图中涉及边长均不小于0，且不超过10000。

输出

输出一个整数，表示1号点到n号点的最短距离。

如果路径不存在，则输出-1。

输入样例

3 3
1 2 2
2 3 1
1 3 4

输出样例

3

算法思想

在正权稀疏图中，常用的最短路算法是堆优化的Dijkstra算法
由于Dijkstra算法需要使用最小值对其他结点进行松弛操作
使用堆这一数据结构可以大大提高此算法的时间复杂度
若图中有n个结点，m条边,则此算法的时间复杂度为
$O(m*log(n))$

示例代码

#include<bits/stdc++.h>
using namespace std;
const int N = 150010, MAXN = 0x3f3f3f3f;
int h[N], e[N], ne[N], w[N], idx;
int st[N], dis[N];
typedef pair<int, int> PII;

priority_queue<PII, vector<PII>, greater<PII> > heap;

int n, m;
void add(int a, int b, int d)
{
    e[idx] = b;
    w[idx] = d;
    ne[idx] = h[a];
    h[a] = idx ++;
}
int d()
{
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    heap.push({0,1});
    while(heap.size())
    {
        PII t=heap.top();
        heap.pop();
        int d=t.first,u=t.second;
        if(st[u])continue;
        st[u]=1;
        for(int i=h[u];i!=-1;i=ne[i])
        {
            int v=e[i];
            if(dis[v]>d+w[i])
            {
                dis[v]=d+w[i];
                heap.push({dis[v],v});
            }
        }
    }
    if(dis[n]==MAXN)
        return -1;
    else
        return dis[n];
}
int main()
{
    memset(h, -1, sizeof h);

    scanf("%d%d", &n, &m);

    for(int i = 1;i <= m; i++){
        int a, b, d;
        scanf("%d%d%d", &a, &b, &d);
        add(a, b, d);
    }

    int t = d();
    printf("%d\n", t);

    return 0;
}