C++ 解法, 执行用时: 121ms, 内存消耗: 2308K, 提交时间: 2021-12-21 19:17:41

#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;
const int inf=1e9;
int g[maxn][maxn],n,m;
int main () {
	scanf("%d%d",&n,&m);
	for (int i=0;i<=n;i++) for (int j=0;j<=n;j++) g[i][j]=inf;
	while (m--) {
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		g[u][v]=min(g[u][v],w);
	}
	for (int k=1;k<=n;k++) for (int i=1;i<=n;i++) for (int j=1;j<=n;j++)  {
		if (i!=j) {
			g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
		}
	}
	if (g[1][n]==inf) printf("-1");
	else printf("%d\n",g[1][n]);
}