[数据结构与算法]Dijkstra求最短路

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

s首先看这道题的数据范围，m 是近似于n^2级别的，对于稠密图，用朴素版的dijkstra即可。

我们用邻接矩阵来存储两点之间的距离，先将所有距离设置成无穷，因为存在重边，所以我们只要对两个值取min就可以了。然后用d数组来存储这些点到1的距离，同样先初始化为无穷大，此时可以更新d[1] = 0 ，然后每次选出最小距离的点来对其他点进行更新。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std ;
const int INF = 0x3f3f3f3f ;
int n , m ;
int g[550][550] , dist[550];
bool st[550] ;//用布尔数组来判断这点有没有使用过
int dijkstra()
{
    memset(dist , 0x3f , sizeof dist) ;//将1到n的所有点距离初始化为无穷大
    dist[1] = 0 ;//1到1的距离为0
   
    for(int i = 1 ; i <= n ; i ++)//更新n次
    {
        int t = -1 ;
        for(int j = 1 ; j <= n ; j ++)
        {
            if(!st[j] && (t == -1 || dist[j] < dist[t])) t = j ;//找出距离最近的点
        }
        
        st[t] = true ;
        for(int k = 1 ; k <= n ; k ++)用这个点来对其他点实现更新
        {
            if(dist[k] > dist[t] + g[t][k]) 
                dist[k] = dist[t] + g[t][k] ;
        }
    }
    
    if(dist[n] == INF) return -1 ;//如果两者之间距离为无穷大，那么说明没有从1到n的路径
    else return dist[n] ;
}
int main()
{
    cin >> n >> m ;
    memset(g , 0x3f , sizeof g) ;//将所有值设置成无穷
    while(m --)
    {
        int a , b , c ;
        scanf("%d%d%d",&a,&b,&c) ;
        g[a][b] = min(g[a][b] , c) ;//在原值和新读入的值之间选择最小值即可
    }
    
    int t = dijkstra() ;
    printf("%d\n",t) ;//输出t
    return 0 ;
}