题目描述

blablabla

样例

blablabla

(暴力枚举)

首先声明几个变量
1. dist[i]: i 到 1 的最短距离
2. st[i] : 若为 true， 表示节点 i 已经找到了最短距离

$\color{red}{过程：}$
将dist 和 g 都初始化为正无穷
循环 n 次（也可以 n - 1 次）， 目的是为了找到当前最短路径（第一短， 第二短 ， ……）
　　每次从dist 中找出最短路径，设为 t； 找到以后将他的 st 改成 true， 表示这个点的最短距离已经确定了

遍历一遍这个点的出边，若是从他经过的点可以使距离变得更短，就要更改一下
　　　　这里注意一下，不必 if(!st[i]); 因为若是存在一点 x 已经找到了最短距离，就不会因为 t 而发生变化

时间复杂度

$O(n^2)$

参考文献

C++ 代码

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

const int N = 510;
int g[N][N]; //邻接矩阵
int n ,m;
bool st[N]; // 是否在当前已经找到的最短路径的集合中
int dist[N]; // 分别表示每个点到 1 的最短距离

int dijkstra()
{
    dist[1] = 0;
    for(int j = 0; j < n; j++)
       {
           int t = -1;
           for(int i = 1; i <=n; i ++)
           {
               if(!st[i] && (t == -1 || dist[i] < dist[t])) 
               {
                   t = i;
               }
           }

           st[t] = true; // 把这个点加入到已经找到最短路径的集合、

           for(int i = 1; i <=n; i++) 
             //if(!st[i])
               dist[i] = min(dist[i], dist[t] + g[t][i]);
       }

     if(dist[n] == 0x3f3f3f3f) return -1;
     else return dist[n];
}
int main()
{
    memset(dist, 0x3f, sizeof dist);
    memset(g, 0x3f, sizeof g);
    cin>>n>>m;
    int a, b, c;
    while(m--)
    {
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = min(g[a][b], c);
    }

    int t = dijkstra();
    cout<<t;
}