给定一个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
输出样例:
3
dijkstra算法
稠密图用邻接矩阵求o(n^2)
#include<bits/stdc++.h>
using namespace std;
typedef int ll; //int是四个字节经memset(g,0x3f,sizeof(g))后每个字节为
const int N=1010; //3f 所以值为0x3f3f3f3f;
int g[N][N]; //存放两个点之间的距离;
int d[N]; //存放每个点到起点的距离;
int st[N]; //判断每个点到起点的距离是否已经是最小值;
int n,m;
ll dijkstra()
{
d[1]=0; //初始化起点到起点的距离为0;
for(ll i=0;i<n;i++) //n次循环每次找到一个点到起点距离的最小值;
{
ll t=-1; //一开始t的赋值是-1如果t没有被更新,那么要更新一下t;
for(ll j=1;j<=n;j++)
if(!st[j]&&(t==-1||d[t]>d[j]))t=j; //找到目前距离起点最近的点
//这个点到起点的距离是否已经是最小值
st[t]=1; //标记;
for(ll j=1;j<=n;j++) //用这个点到起点的距离更新其他点到起点的距离;
if(!st[j])d[j]=min(d[j],d[t]+g[t][j]);
}
if(d[n]==0x3f3f3f3f)return -1;
return d[n];
}
int main()
{
memset(g,0x3f,sizeof(g));// memset按字节赋值,所以memset 0x3f 就等价与赋值为0x3f3f3f3f;
memset(d,0x3f,sizeof(d));
cin>>n>>m;
for(ll i=0;i<m;i++)
{
ll x,y,z;
cin>>x>>y>>z;
g[x][y]=min(g[x][y],z);
}
cout<<dijkstra()<<endl;
}