题目链接：Dijkstra求最短路 I

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 510;int n, m;
int g[N][N];
int dist[N];
bool st[N];int dijkstra()
{memset(dist, 0x3f, sizeof dist);dist[1] = 0;for(int i = 0; i < n; i++){// t 代表没有确认的最短路长度的最小值int t = -1;for(int j = 1; j <= n; j ++){if(!st[j] && (t == -1 || dist[t] > dist[j])){t = j;}}st[t] = true;// 更新其他点的距离for(int j = 1; j <= n; j++){dist[j]  = min(dist[j], dist[t] + g[t][j]);}}if(dist[n] == 0x3f3f3f3f) return -1;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;
}