本文主要是介绍ACwing 850. 堆优化Dijkstra求最短路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给定一个 nn 个点 mm 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。
请你求出 11 号点到 nn 号点的最短距离，如果无法从 11 号点走到 nn 号点，则输出 −1−1。
输入格式
第一行包含整数 nn 和 mm。
接下来 mm 行每行包含三个整数 x,y,zx,y,z，表示存在一条从点 xx 到点 yy 的有向边，边长为 zz。
输出格式
输出一个整数，表示 11 号点到 nn 号点的最短距离。
如果路径不存在，则输出 −1−1。
数据范围
1≤n,m≤1.5×1051≤n,m≤1.5×105,
图中涉及边长均不小于 00，且不超过 1000010000。
输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
3
#include<bits/stdc++.h>
#define lu pair<int,int>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 2e5;
struct node
{int v,next,w;
}edge[maxn];
int cnt;
bool vis[maxn];
int dis[maxn],head[maxn];
void add(int u,int v,int w)
{edge[cnt].w=w;edge[cnt].v=v;edge[cnt].next=head[u];head[u]=cnt++;
}
void dijkstra(int n)
{priority_queue<lu,vector<lu>,greater<lu>>q;memset(dis,inf,sizeof dis);q.push({0,1});dis[1]=0;while(!q.empty()){lu temp = q.top();q.pop();int u = temp.second;if(vis[u]) continue;vis[u]=true;for(int i = head[u];i!=-1;i=edge[i].next){int v = edge[i].v;if(dis[v]>dis[u]+edge[i].w){dis[v]=dis[u]+edge[i].w;q.push({dis[v],v});}}}if(dis[n]==inf) cout<<-1<<endl;else cout<<dis[n]<<endl;
}
int main()
{int n,m,u,v,w;cin>>n>>m;memset(head,-1,sizeof(head));for(int i = 0;i<m;i++){scanf("%d%d%d",&u,&v,&w);add(u,v,w);}dijkstra(n);return 0;
}
这篇关于ACwing 850. 堆优化Dijkstra求最短路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
