欢迎访问==> 【考研OR保研】机试题
题目描述
给定一个 $n$ 个点 $m$ 条边的有向图,图中可能存在重边和自环,所有边权均为正值。
请你求出 $1$ 号点到 $n$ 号点的最短距离,如果无法从 $1$ 号点走到 $n$ 号点,则输出 $\-1$。
输入格式
第一行包含整数 $n$ 和 $m$。
接下来 $m$ 行每行包含三个整数 $x,y,z$,表示存在一条从点 $x$ 到点 $y$ 的有向边,边长为 $z$。
输出格式
输出一个整数,表示 $1$ 号点到 $n$ 号点的最短距离。
如果路径不存在,则输出 $\-1$。
数据范围
$1 \\le n \\le 500$,
$1 \\le m \\le 10^5$,
图中涉及边长均不超过10000。
输入样例:
3 3
1 2 2
2 3 1
1 3 4
输出样例:
3
C++ 代码
/*
变量解释:
S:起点 T:终点
st[i]表示i号点是否已经确定了到起点的最短距离
d[i]表示第i号点到起点的距离
算法步骤:
1、初始化距离数组d,d[S] = 0,其他初始化为正无穷,表示不可达
2、遍历n次
3、每次循环找到一个还没有确定最短距离【并且】在还没有确定最短距离点中d[i]最小的点
4、将该点标记为已经确定了最短距离
5、用该点更新其他点到起点S距离
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int g[N][N], n, m, d[N];
bool st[N];
int djikstra()
{
//初始化距离数组d
memset(d, 0x3f, sizeof d);
d[1] = 0;
//循环n次
for(int i = 0; i < n; i ++)
{
//每次循环找到一个还没有确定最短距离【并且】在还没有确定最短距离点中d[i]最小的点
int t = -1;
for(int j = 1; j <= n; j ++)
{
if(!st[j] && (t == -1 || d[j] < d[t])) t = j;
}
//将该点标记为已经确定了最短距离
st[t] = true;
//用该点更新其他点到起点S距离
for(int j = 1; j <= n; j ++)
{
d[j] = min(d[j], d[t] + g[t][j]);
}
}
return d[n];
}
int main()
{
memset(g, 0x3f, sizeof g);
cin >> n >> m;
while(m -- )
{
int a, b, c;
cin >> a >> b >> c;
g[a][b] = min(g[a][b], c);
}
int res = djikstra();
if(res == INF) cout << -1 << endl;
else cout << res << endl;
return 0;
}