欢迎访问==> 【考研OR保研】机试题
题目描述
给定一个 $n$ 个点 $m$ 条边的有向图,图中可能存在重边和自环,所有边权均为非负值。
请你求出 $1$ 号点到 $n$ 号点的最短距离,如果无法从 $1$ 号点走到 $n$ 号点,则输出 $\-1$。
输入格式
第一行包含整数 $n$ 和 $m$。
接下来 $m$ 行每行包含三个整数 $x,y,z$,表示存在一条从点 $x$ 到点 $y$ 的有向边,边长为 $z$。
输出格式
输出一个整数,表示 $1$ 号点到 $n$ 号点的最短距离。
如果路径不存在,则输出 $\-1$。
数据范围
$1 \\le n,m \\le 1.5 \\times 10^5$,
图中涉及边长均不小于 $0$,且不超过 $10000$。
数据保证:如果最短路存在,则最短路的长度不超过 $10^9$。
输入样例:
3 3
1 2 2
2 3 1
1 3 4
输出样例:
3
C++ 代码
该题是对【Dijkstra求最短路1】的优化,具体请参考Djkstra求最短路1
/*
在【Dijkstra求最短路1】中的第三步:每次循环找到一个还没有确定最短距离【并且】在还没有确定最短距离点中d[i]最小的点
在【Dijkstra求最短路2】中这一步我们使用优先队列(堆)来进行优化,其余无变化
易错点:【h数组初始化】【优先队列要用小根堆】
*/
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int, int> pii;
const int N = 200010, INF = 0x3f3f3f3f;
int h[N], e[N], w[N], nxt[N], idx;
int n, m, d[N];
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, nxt[idx] = h[a], h[a] = idx ++;
}
int djikstra()
{
priority_queue<pii, vector<pii>, greater<pii> > q;
//初始化距离数组d
memset(d, 0x3f, sizeof d);
d[1] = 0;
q.push({d[1], 1});
while(q.size())
{
pii t = q.top();
q.pop();
int var = t.y, dis = t.x;
if(st[var]) continue;
st[var] = true;
for(int i = h[var]; i != -1; i = nxt[i])
{
int j = e[i];
if(d[j] > dis + w[i])
{
d[j] = dis + w[i];
q.push({d[j], j});
}
}
}
return d[n];
}
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m;
while(m -- )
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
int res = djikstra();
if(res == INF) cout << -1 << endl;
else cout << res << endl;
return 0;
}