最短路变形

题目点这里
要注意，输出的是最大的能通过的货物重量，只需要在原来最短路代码上修改一下就可。

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
const	int N=2010;
int d[N],g[N][N];
bool vis[N];
int n,m;
int h;
int v;
void djs()
{
   
		for(int i=1;i<=n;i++)
		{
   d[i]=g[1][i];
		}
	for(int i=1;i<=n;i++)
	{
   
		int f=-1;
		for(int j=1;j<=n;j++)
		{
   
			if(!vis[j]&&f<d[j])
			{
   
			v=j;
			f=d[j];}
		// printf("%d\n",t);
		}
		vis[v]=1;
		for(int j=1;j<=n;j++)
		{
   
			if(d[j]<min(d[v],g[v][j]))
			d[j]=min(d[v],g[v][j]);
		// printf("%d\n",t);
		}
	}
}
int main()
{
   
	int t;
	int k=0;
	scanf("%d",&t);
	while(t--)
	{
   
		memset(vis,0,sizeof(vis));
		memset(g,0,sizeof(g));
		scanf("%d%d",&n,&m);
		while(m--)
		{
   
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			g[a][b]=g[b][a]=c;
		}
		djs();
		printf("Scenario #%d:\n",++k);
		printf("%d\n\n",d[n]);
	}
	return 0;
}