Dijkstra求单源最短路

849. Dijkstra求最短路 I

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

输入样例：

输出样例：

* Dijkstra 算法：单源最短路径问题；
* 将源点的距离设置为0，接下来Nv轮循环，找出还未被加入集合且离源点最近的顶点，
* 如果时找到的这个顶点与源点有路相通，则这个顶点与源点的距离一定是这个顶点与源点之间
* 的距离最短的，不可能从源点途径另外一个顶点到达此顶点的距离更小（如果有，那么一定还有
* 与此点未连通且离源点的距离更小的点，并且是正权图，所以与前面的话（找出还未被加入集合
* 且离源点最近的顶点）矛盾），所以此算法正确；


/**
 * Dijkstra 算法：单源最短路径问题；
 * 将源点的距离设置为0，接下来Nv轮循环，找出还未被加入集合且离源点最近的顶点，
 * 如果时找到的这个顶点与源点有路相通，则这个顶点与源点的距离一定是这个顶点与源点之间
 * 的距离最短的，不可能从源点途径另外一个顶点到达此顶点的距离更小（如果有，那么一定还有
 * 与此点未连通且离源点的距离更小的点，并且是正权图，所以与前面的话（找出还未被加入集合
 * 且离源点最近的顶点）矛盾），所以此算法正确；
*/
 
#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int maxn = 510,INF=1e9;
int G[maxn][maxn]; //邻接矩阵
int d[maxn]; //距离数组
bool hs[maxn]; //记录顶点是否被选择
int Nv,Ne; //顶点数，边数
 
void Read() //读入数据
{
    fill(*G,*G+maxn*maxn,INF);
    cin >> Nv >> Ne;
    for(int i=0;i<Ne;++i)
    {
        int u,v,w;
        cin >> u >> v >> w;
        G[u][v]=min(G[u][v],w); //存在重边，选择权值最小的边即可
    }
}
 
int Dijkstra(int st) //各点到st顶点的最短距离
{
    fill(d,d+maxn,INF); 
    d[st]=0;    //源点的距离为0
    
    for(int i=0;i<Nv;++i)
    {
        int u=-1,MIN=INF;
        for(int j=1;j<=Nv;++j)
            if(hs[j]==0 && d[j]<MIN)
            {
                MIN=d[j];
                u=j;
            }
            
        if(u==-1)   //如果u等于-1，说明图不连通
            return -1;
        hs[u]=1;
        for(int v=1;v<=Nv;++v)
            if(G[u][v]!=INF && hs[v]==0 && d[u]+G[u][v]<d[v]) //u，v有边且v还未被选中
                d[v]=d[u]+G[u][v];  //且从源点到v途径u能使源点到v的距离变小
    }
    
    return d[Nv];  
}
 
int main()
{
    Read();
    
    cout << Dijkstra(1) << endl;
 
    return 0;
    
}

850. Dijkstra求最短路 II