题目描述

给定一个 $n$ 个点 $m$ 条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出 $1$ 号点到 $n$ 号点的最短距离，如果无法从 $1$ 号点走到 $n$ 号点，则输出 $−1$。

输入格式

第一行包含整数 $n$ 和 $m$ ( $1 \le n \le 500$，$1 \le m \le 100000$ )。

接下来 $m$ 行每行包含三个整数 $x$，$y$，$z$，表示存在一条从点 $x$ 到点 $y$ 的有向边，边长为 $z$ ( $1 \le z \le 10000$ )。

输出格式

输出一个整数，表示 $1$ 号点到 $n$ 号点的最短距离。

样例

3 3
1 2 2
2 3 1
1 3 4

3

完成程序

#include<bits/stdc++.h>
using namespace std;
const int N = 500 + 10;
int arcs[N][N], dist[N], n, m;
bool f[N];
void dij(){
	dist[1] = 0;//初始化
	for (int i=1;i<=n;i++){ //最多循环 n-1 次，每次选择一个点加入集合
		int t = -1;
		for (int j = 1; j<= n; j++){ //寻找值最小的点
			if (f[j] == 0 && (t == -1 || __填空(1)__ < dist[t])){
				t = j;
			}
		}
		if(dis[t]==0x3f3f3f3f) return;

		f[t] = 1;//标志位，把点加入集合
		for (int k = 1; k <= n; k++) { //更新dist的值
			if (f[k] == 0 && __填空(2)__) {
				dist[k] = dist[t] + arcs[t][k];
			}
		}
	}
	return;
}

int main(){
	cin >> n >> m;//输入点数和边数
	memset(dist, 0x3f3f3f3f, sizeof dist);
	memset(arcs, 0x3f3f3f3f, sizeof arcs);
	for (int i = 1; i <= m; i++) {
		int x, y,z;
		cin >> x >> y >> z;
		arcs[x][y] = min(__填空(3)__,z);//每次更新为最小值
	}
	dij();
	if (dist[n] == 0x3f3f3f3f) cout << -1 << endl;
	else cout << dist[n] << endl;

	return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}