嗨嗨嗨，我发现我上上周居然没有写题解，作为一名寄宿制学校的学生，一周才回来一次，必须写一个！

此题，依题知，宜Dijkstra算法，算法的本质与floyed我觉得有点像，基本上就是去找到最近的点，而后判断 由1到 j 与 由1到t再到j 哪个更短，但为了避免重复，还记得用数组记录是否搜索过（有点像dfs）

/*
d[i]表示由一到i的当前最短距离
*/
int dijkstra(){
	memset(d,0x3f,sizeof d);
	d[1]=0;//由一到一的距离为零
	for(int i=0;i<n;i++){
		int t=-1;
		for(int j=1;j<=n;j++){
			if(!st[j]&&(t==-1||d[t]>d[j]))
				t=j;
		}//判断由1到 j 与 由1到t再到j 哪个更短
		st[t] = true;//将t定义为已经走过
		for(int j=1;j<=n;j++)
			d[j]=min(d[j],d[t]+g[t][j]);//用t去改变d[j],即改变当前最短路！
	}
	if (d[n] > 0x3f3f3f3f / 2) return -1;//退出
	else return d[n];
}

现在搜索完了，输入输出会自己写吧，以下为完整代码，有问题私信（苕别来！！！）！

#include <bits/stdc++.h>
using namespace std;
const int N=510;
int n,m,x,y,z;
int g[N][N],d[N];
bool st[N];
int dijkstra(){
	memset(d,0x3f,sizeof d);
	d[1]=0;
	for(int i=0;i<n;i++){
		int t=-1;
		for(int j=1;j<=n;j++){
			if(!st[j]&&(t==-1||d[t]>d[j]))
				t=j;
		}
		st[t] = true;
		for(int j=1;j<=n;j++)
			d[j]=min(d[j],d[t]+g[t][j]);
	}
	if (d[n] > 0x3f3f3f3f / 2) return -1;
	else return d[n];
}
int main() {
	cin>>n>>m;
	memset(g, 0x3f, sizeof g);
	while(m--) {
		cin>>x>>y>>z;
		g[x][y]=min(g[x][y], z);
	}
	int t = dijkstra();
	cout << t << endl;

	return 0;
}

Dijkstra||别问我，我也不会，😕