题目

代码：

#include<bits/stdc++.h>
#define N 114514
using namespace std;
int city[2001][2001],dis[2001],p[2001];
int n,m,num,ans=0,s;

int main()
{
	memset(city,N,sizeof(city));
	memset(dis,N,sizeof(dis));
	memset(p,true,sizeof(p));
	cin>>n>>m;
	num=n;
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		city[a][b]=city[b][a]=min(c,city[a][b]);
	}
	for(int i=2;i<=n;i++)
	{
		dis[i]=city[1][i];
	}
	s=1;
	dis[s]=0;
	while(--num)
	{
		p[s]=false;
		int mins=N;
		int minc;
		for(int j=1;j<=n;j++)
		{
			if(city[s][j]<mins&&p[j])
			{
				mins=city[s][j];
				minc=j;
			}
		}
		//cout<<"dis_minc "<<dis[minc]<<' ';
		dis[minc]=min(dis[minc],(dis[s]+mins));
		//cout<<"minc "<<minc<<' '<<"dis_s "<<dis[s]<<' '<<"mins "<<mins<<' '<<"dis_minc "<<dis[minc]<<endl;
		for(int j=1;j<=n;j++)
		{
			if(j!=minc)
				city[minc][j]=city[j][minc]=min(city[s][j],city[minc][j]);
		}
		s=minc;
		if(s==n)
		{
			p[n]=false;
		}
		//cout<<"news "<<s<<endl;
	}
	if(p[n])
		cout<<-1<<endl;
	else
		cout<<dis[n]<<endl;
	return 0;
}