题目描述
给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,所有边权均为正值。
请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出 −1。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。
输出格式
输出一个整数,表示 1 号点到 n 号点的最短距离。
如果路径不存在,则输出 −1。
数据范围
1≤n≤500,
1≤m≤105,
图中涉及边长均不超过10000
样例
输入样例:
3 3
1 2 2
2 3 1
1 3 4
输出样例:
3blablabla
朴素dijkstra算法,看代码
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int p=510;
int g[p][p];//邻接矩阵,用二位数组的方式来表示点与点的距离
int d[p];//表示每个点距离起点的距离
bool st[p];//确定为最短路以及判断是否这个点是否是最小距离起点的点
int n,m;
int dijkstra()
{
memset(d,0x3f,sizeof d);//将距离全都初始化为无穷大
d[1]=0;//第一个点1距离起点1为0
//依次求出每个点距离起点1的最小值
for(int i=0;i<n;i++)
{
int t=-1;//定义一个t便于赋初值且更新距离起点最小的点
for(int j=1;j<=n;j++)//这个循环判断距离起点最小的点
{
if(!st[j]&&(t==-1||d[t]>d[j]))//当t=-1时先初始化t,如果不是最小距离点且d[j]距离
//起点最小
t=j;
}
st[t]=1;//将这个最小距离点存入s数组
for(int j=1;j<=n;j++)//将最小距离点存入后,根据这个点依次更新每个点距离起点的距离
//如果没有t到j的点则距离为无穷大,后续循环总会找到最小距离点与j的点的g值并更新最小值
d[j]=min(d[j],d[t]+g[t][j]);
}
if(d[n]==0x3f3f3f3f) return -1;//如果到不了n号点则距离为无穷大
return d[n];//否则返回这个距离
}
int main()
{
cin>>n>>m;
memset(g,0x3f,sizeof g);//初始化邻接矩阵
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
g[a][b]=min(g[a][b],c);//将每个点之间的距离用二位数组表示
}
cout<<dijkstra();
return 0;
}