题目描述

给定一个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

C++ 代码

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int N=510;

int n,m;           //n是结点个数，m是边的条数
int g[N][N];       //g[a][b]是指a到b的距离
int dis[N];        //存储每一个边到第一个点的距离
bool st[N];        //存储一个点的最短距离是否已经确定

int dijkstra()
{
    memset(dis,0x3f,sizeof dis);     //初始化所有点到第一个点的距离为正无穷
    dis[1]=0;                        //让第一个点的距离为0

    for(int i=1;i<=n;i++)            //循环n次 
    {
        int t=-1;                    //存储距离第一个点最短的点的数值
        for(int j=1;j<=n;j++)        //找到当前状态下距离第一个点最短的点
        {
            if(st[j]==false && (t==-1 || dis[t]>dis[j]))  //如果当前点最短距离没有确定、t==-1（是第一个点）或者这个点的最短距离更短
               t=j;                  //将t等于更新后的最短距离
        }

        for(int j=1;j<=n;j++)         //更新每一个点到第一个点的最短距离
        {
            dis[j]=min(dis[j],dis[t]+g[t][j]);  //当前点的最短距离=之前的最短距离与现在最短距离t的距离+t和j之间的距离 两者的最小值
        }

        st[t]=true;    //因为这个t的最短距离已经确定，让这个点的st=true
    }

    if(dis[n]==0x3f3f3f3f) return -1;  //如果n这个点的距离还是初始的正无穷，说明没有循环到他，说明不存在最短路径
    else return dis[n];   //else 返回n到第一个点的最短距离
}

int main()
{
    scanf("%d%d",&n,&m);        //输入结点个数和边的条数
    memset(g,0x3f,sizeof g);    //使所有的g数组初始化为正无穷

    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);//输入a和b连接，长度为c

        g[a][b]=min(g[a][b],c);   //因为可能会有重边，所以在a和b中的边长度取最小值
    }

    printf("%d",dijkstra());       //输出Dijkstra返回的第n个数到第一个数的最短路长度

    return 0;
}