849. Dijkstra求最短路 I

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

请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。

输入格式

第一行包含整数n和m。

接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。

输出格式

输出一个整数，表示1号点到n号点的最短距离。

如果路径不存在，则输出-1。

数据范围

1≤n≤5001≤n≤500,
1≤m≤1051≤m≤105,
图中涉及边长均不超过10000。

输入样例：

3 3

1 2 2

2 3 1

1 3 4

输出样例：

3

使用条件：
单源最短路
无负边条件

朴素 Dijkstra 算法

因为n与m差太多，是个稠密图，所以用邻接矩阵来存

稀疏图用邻接表存

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

//500个点 1e5条边，所以用邻接矩阵来写

const int N = 510;

int n,m;

int g[N][N];//邻接矩阵

int dist[N];//dijkstra的距离,表示从1到n的最短距离,当前的最短距离

bool st[N];//表示每个点的最短路是否确定

//边权为正所以不可能存在自环,重边的话只用保留两条边长度最短的那条边

int dijkstra(){

    //首先初始化距离,初始化为正无穷

    memset(dist,0x3f,sizeof dist);

    //一号点的距离初始化为0

    dist[1] = 0;

    //迭代n次,找最短路

    for(int i = 0;i < n;i++){

        //每一次第一步先找到在每一次还没确定的最短路长度的点当中,距离最小的那一个路径长度

        int t = -1;//表示还没有确定

        //遍历所有的点

        for(int j =  1;j <= n;j ++)

        //如果当前这个点还没有确定最短路的话

        //并且

        //当前的点还没确定 或者 当前的t不是最短的距离

            if(!st[j] && (t == -1 || dist[t] > dist[j]))

                t = j;

        st[t] = true;

        //用t来更新其他点的距离

        for(int j = 1;j <= n;j++)

            //用1~t的距离加上t~j的这个边,来更新1~j这条边

            dist[j] = min(dist[j],dist[t] + g[t][j]);

    }

    //1~n是不连通的

    if(dist[n] == 0x3f3f3f3f) return -1;

    //否则返回1~n的最短距离

    return dist[n];

}

int main(){

    scanf("%d%d",&n,&m);

    //初始化邻接矩阵

    // for(int i = 0;i <= n;i++)

    //     for(int j = 0;j <= n;j++){

    //         if(i == j) g[i][j] = 0;

    //         else g[i][j] = INF;

    //     }

    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);//取min原因是a,b之间可能会有多条边,保留边的最短距离

    }

    int t = dijkstra();

    printf("%d\n",t);

    return 0;

}

　　

849. Dijkstra求最短路 I的相关教程结束。