AcWing 849. Dijkstra求最短路 I
原题链接
简单
作者:
X_320
,
2024-05-01 20:19:43
,
所有人可见
,
阅读 1
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stack>
#include <set>
#include <vector>
#include <queue>
#include <stdlib.h>
#include <stdio.h>
#include <map>
#include<cmath>
#include<iomanip>
using namespace std;
#define mp make_pair
#define re return
#define fr for
#define sr sort
#define ii int
#define db double
#define ll long long
#define el else
#define ccspeed ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef pair<int, int> pii;
const ii N = 510;
const ii inf = 0x3f3f3f3f;
ii n, m;
ii g[N][N];//长度
ii dist[N];//最短路径长
bool st[N];
ii disa() {
memset(dist, inf, sizeof dist);//初始化,方便比较
dist[1] = 0;
fr(ii i = 0; i < n; i++) {//循环n个点
ii t = -1;//要找每个点到下个点的最短路径,t为标计
fr(ii j = 1; j <= n; j++)
if (!st[j] && (t == -1 || dist[t] > dist[j]))//dist[t]>dist[j])发现更小的路径
t = j;
st[t] = true;
fr(ii j = 1; j <= n; j++)
dist[j] = min(dist[j], dist[t] + g[t][j]);//比较1到j距离和1到t+t到j的距离和大小,取最小
}
if (dist[n] == inf) re -1;//说明不连通
re dist[n];
}
int main() {
ccspeed;
cin >> n >> m;
memset(g, inf, sizeof g);//初始化
while (m--) {
ii a, b, c;
cin >> a >> b >> c;
g[a][b] = min(g[a][b], c);//a,b间可能有多条边,保留最短边即可
}
ii t = disa();
cout << t << "\n";
re 0;
}