题目描述

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

主要考点

朴素版dijkstra

姊妹题

Dijkstra求最短路 II

时间复杂度$O(n ^ 2)$

C ++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 510;

int g[N][N];// 存储每条边的边权
int dist[N];//g[j] 存储 1 号点到 j号点的距离
bool st[N];//st[t]表示: t 号点是否已经更新过其他点
int n, m;

int dijkstra(){
    //初始化距离
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    //因为已经加入一号点
    for(int i = 0; i < n - 1; i ++){
        //寻找距离1号点最近的点
        int t = -1;//t用来求所有st[] == false的节点中，dist[]最小的节点编号
        for(int j = 1; j <= n; j ++){
            if(!st[j] && (t == -1 || dist[j] < dist[t])){
                t = j;
            }
        }

        // 用t更新其他点的距离
        for(int j = 1; j <= n; j ++){
            //1 号点通过 t号点到达 j 号点的最短距离
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }//本题中边权都为正数,dist[i] + g[i][i] 一定大于 dist[i]，所以i->i这条边一定不会被用到。

        st[t] = true;//t已经用过,置为false
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

int main(){
    cin >> n >> m;

    memset(g, 0x3f, sizeof g);
    for(int i = 0; i < m; i ++){
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);
    }

    cout << dijkstra() << endl;

    return 0;
}