迪杰斯特拉（dijkstra）算法

朴素版迪杰斯特拉算法

适用范围：处理权值为正的最短路问题

步骤：

初始化d[1]=0，其他d[n]=INT_MAX
s中放入已经确定最短路的点
遍历，把不在s中的距离最近的点，加入到s
- 更新所有点的距离

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

#include<iostream>
#include<cstring>
using namespace std;

const int N=550;	//N表示点的数量
int a[N][N],d[N];	//d表示当前节点到1号点的距离
bool v[N];			//v表示当前节点是否已经确定最短路
int n,m;
    
int dijkstra()
{
    memset(d,0x3f3f3f3f,sizeof(d));	//初始化距离为无穷
    d[1]=0;		//1号点到1号点的距离为0
    for(int i=1;i<=n;i++)			//n个点进行n次遍历
    {
        int t=-1;		//作为起点
        for(int j=1;j<=n;j++)
        {
            if(!v[j]&&(t==-1||d[t]>d[j]))	//当前点没确定最短距离
            {							//且第一次遍历或距离比现在大
                t=j;	//更新距离
            }
        }
        v[t]=true;		//确定最短路
        for(int j=1;j<=n;j++)		//对于确定的最短路更新每个节点的距离
        {
            d[j]=min(d[j],d[t]+a[t][j]);
        }
    }
    
    if(d[n]==0x3f3f3f3f) return -1;			
    return d[n];
}

int main()
{

    cin>>n>>m;
    memset(a,0x3f3f3f3f,sizeof(a));
    while(m--)
    {
        int x,y,z;
        cin>>x>>y>>z;
        a[x][y]=min(a[x][y],z); //防止两个点之间有多条边，只保留最小边
    }
    
    cout<<dijkstra();
}

堆优化版迪杰斯特拉算法

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。