题目描述
给定一个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;
}