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。
输入样例：

3 3
1 2 2
2 3 1
1 3 4

输出样例：

3

这个题的点的数量大小很小，我们需要用邻接矩阵来存
用一个 dist 数组保存源点到其余各个节点的距离，dist[i] 表示源点到节点 i 的距离。初始时，dist 数组的各个元素为无穷大。
用一个状态数组 state 记录是否找到了源点到该节点的最短距离，state[i] 如果为真，则表示找到了源点到节点 i 的最短距离，state[i] 如果为假，则表示源点到节点 i 的最短距离还没有找到。初始时，state 各个元素为假。

代码

#include <bits/stdc++.h>
using namespace std;
int g[505][505];
int d[100005],st[100005];
int n,m;
int Dijkstra(){
    memset(d,0x3f,sizeof d);
    d[1] = 0;
    for(int i = 0; i < n; i ++){
        int t = -1;
        for(int j = 1; j <= n; j ++){
            if(!st[j] && (t == -1 || d[t] > d[j])) t = j;
        }
        st[t] = true;
        for(int j = 1; j <= n; j ++){
            d[j] = min(d[j],d[t] + g[t][j]);
        }
    }
    return d[n];
}
int main(){
    memset(g,0x3f,sizeof g);
    cin >> n >> m;
    for(int i = 1; i <= m; i ++){
        int a,b,c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b],c);
    }
    if(Dijkstra() == 0x3f3f3f3f){
        cout << -1 << endl;
    }else{
        cout << d[n] << endl;
    }
    return 0;
}