随便地打了个dij然后——

本程序是50分

#include<cstdio>
#define ll long long

const int N = 2505;
const ll INF = 100000000000;

ll f[N][N];
ll p[N];
ll dis[N]; 
ll a,b,c;
ll n,m;

int main()
{
	scanf("%lld%lld",&n,&m);
	
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<=n;j++)
		{
			f[i][j]=INF;
		}
	}
	
	for(ll i=1;i<=m;i++)
	{
		scanf("%lld%lld%lld",&a,&b,&c);
		if(f[a][b]==INF)
			f[a][b]=f[b][a]=c;
	}
	
	p[1]=1;
	dis[1]=0;
	
	for(ll i=1;i<=n;i++)
	{
		dis[i]=f[1][i];
	}
	
	for(ll i=1;i<=n-1;i++)
	{
		ll minn=INF;
		ll k=0;
		
		for(int j=1;j<=n;j++)
		{
			if(p[j]==0 && dis[j]<minn)
			{
				minn=dis[j];
				k=j;
			}
		}
		if(k==0)
		{
			break;
		}
		p[k]=1;
		for(int j=1;j<=n;j++)
		{
			if(dis[k]+f[k][j]<dis[j])
			{
				dis[j]=dis[k]+f[k][j];
			}
		}
	}
	
	printf("%lld\n",dis[n]);
	
	return 0;
}

呃——所以——劳烦哪位大佬——呃——指点一下