题目描述

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

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

输入格式
第一行包含整数n和m。

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

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

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

数据范围
1≤n,m≤105,
图中涉及边长均不超过10000。

样例

输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
3

算法1

(小根堆dijkstra)

dijkstra算法步骤：
step1、初始化。 初始化所有节点到源点的距离为无穷大， 初始化visited[N]全为零，表示所有节点均没有出队
初始化优先队列/小顶堆。greater小顶堆,队头元素最小。队列元素是pair{到源点的距离，节点序号}
step2、源点入队。源点入优先队列/小顶堆。入队以pair形式。
step3、while(优先队列/小顶堆不空){
取出小顶堆的堆顶元素（节点ver，按照到源点的距离排序最小）
堆顶元素出队
visited[ver]置1，即标记节点ver出队
for(遍历与ver节点相连的所有节点i){
if(节点i没有出队 && 节点ver到源点的距离 + 节点ver到节点i的距离 < 节点i到源点的距离) {
更新节点i到源点的距离 = 节点ver到源点的距离 + 节点ver到节点i的距离
pair{节点i到源点的距离，节点序号i}入队
}
}
}

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int m, n;

struct node{
    int index; // 用w边连接的节点 index
    int w;     // 边长 w

};  

const int N = 100010;    
bool vis[N];
int dis[N];
vector<node> g[N];
typedef pair<int,int> PII;  

void dijkstra(){
    // dis[i]代表 节点i 到 节点1 的距离， 初始化dis[i]为无穷大
    for(int i = 1; i <= n; i++){ // start from 1 to n
        dis[i] = INT_MAX;//
    }   
    dis[1] = 0;  // dis[1]代表 节点1 到 节点1 的距离 为 0 
    memset(vis, 0, sizeof(vis)); // 所有的点都没有出队

    priority_queue< PII, vector<PII> , greater<PII> > heap; //greater 小顶堆，队头元素最小
    heap.push( { 0, 1});  // 节点1 入队（优先队列）， {到节点1的距离，节点index}
    while(heap.size()){   // 队不为空 
        auto t = heap.top();  
        heap.pop();
        int ver = t.second; //节点index
        int d   = t.first;  //到节点1的距离
        vis[ver] = 1;       //出队才把vis[ver]置为1，
        // 遍历 与 ver节点 相连的节点
        // g[ver] 存储的 是与节点ver相连的节点信息（包括节点index和边长）
        for(int i = 0; i < g[ver].size(); i++){ 
            // next_node是 与节点ver相连的节点index序号
            int next_node = g[ver][i].index;
            if( vis[ next_node ] == 0 &&  d + g[ver][i].w < dis[next_node ]){
                // 更新 dis[next_node]， 即 节点next_node 到 节点1 的距离 
                dis[next_node] =  d + g[ver][i].w;
                heap.push({dis[next_node] ,next_node });//入队 {到节点1的距离，节点index}
            }   
        }        
    }
}

int main()
{
    cin>> n >> m; // n nodes, m egdes
    int x, y,z;
    node tmp;
    for(int i = 0; i < m ; i ++){
        cin >> x >> y >> z;
        tmp.index = y; // 
        tmp.w = z;
        g[x].push_back(tmp);// g[x]是一个数组，每个元素g[i]的类型是vector<node>, 用来存节点的用边连接的节点和边长
        // 比如g[i] 存储的 是与节点 i 相连的节点信息（包括节点index和边长）
    } 
    dijkstra();
    if(dis[n] != INT_MAX) cout << dis[n];
    else cout << -1;
    return 0;
}