题意分析

本题的背景是雨果·赫维（Hugo Heavy）在货运直升机项目失败后拓展业务，需要从客户建造巨型钢铁起重机的地方运输到所需地点，他有城市的街道、桥梁及允许载重量规划图，需要确定能运输的最大重量。

具体问题为：给定城市的规划图，交叉路口编号从$1$到$n$，街道有重量限制，且所有街道可双向通行。任务是找出从交叉路口$1$（雨果的位置）到交叉路口$n$（客户的位置）能运输的最大重量，保证至少存在一条路径。

输入格式为：第一行是场景数量（城市规划图数量），对于每个城市，第一行给出交叉路口数量$n$（$1 \leq n \leq 1000$）和街道数量$m$，接下来$m$行每行包含三个整数，分别表示街道的起始交叉路口、结束交叉路口以及最大允许重量（重量为正且不大于$1000000$），每对交叉路口间最多有一条街道。

输出格式为：每个场景输出先以“Scenario #i:”开头（$i$从$1$开始），接着一行输出能运输的最大允许重量，最后用一个空行结束该场景输出。

解题思路

本题可使用 Dijkstra 算法的变种来解决。传统的 Dijkstra 算法用于求最短路径，而本题是求从起点到终点的最大承载重量路径。

主要步骤如下：

1. 初始化：
   • 用邻接矩阵 e 存储图的信息，初始时将两点间没有直接连接的边的权值设为一个极小值（这里设为 -111111）。
   • dis 数组用于记录从起点到各个点的最大承载重量，初始化为起点到各点的直接连接的最大承载重量。
   • book 数组用于标记点是否已经确定最大承载重量，初始时所有点都未确定。
2. Dijkstra 算法核心：
   • 每次从未确定最大承载重量的点中选择 dis 值最大的点 u，将其标记为已确定。
   • 对于与 u 相邻的点 v，更新 dis[v] 的值。更新规则是取当前 dis[v]、dis[u] 和 e[u][v] 中的合适值，以保证路径上的最小承载重量最大。
3. 输出结果：
   • 输出每个场景的编号和从起点到终点的最大承载重量，每个场景输出后用空行分隔。

标程

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int e[1001][1001],dis[1000010],book[1001];
int n,m;
int main()
{
	int i,s,t1,t2,t3;
	int j,u,v,max;
	int k=1;
	scanf("%d",&s);
	while(s--)
	{
		int inf=-111111;
		scanf("%d %d",&n,&m);
		//初始化
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=n;j++)
			{
				if(j==i)
					e[i][j]=0;
				else
					e[i][j]=inf;
			}			
		}
		//读入边 
		for(i=1;i<=m;i++)
		{
			scanf("%d%d%d",&t1,&t2,&t3);
			e[t1][t2]=e[t2][t1]=t3;	
		}
		//初始化dis数组
		for(i=1;i<=n;i++)
			dis[i]=e[1][i];
		//book数组初始化
		for(i=1;i<=n;i++)
			book[i]=0;
		book[1]=1; 
		//Dijkstra算法核心语句
		for(i=1;i<n-1;i++)
		{
			max=inf;
			for(j=1;j<=n;j++)
			{
				if(book[j]==0&&dis[j]>max)
				{
					max=dis[j];
					u=j;
				}
			}
			book[u]=1;
			for(v=1;v<=n;v++)
			{
				if(e[u][v]>inf)
				{
					if(dis[v]<dis[u]&&dis[v]<e[u][v])
					{
						if(dis[u]<e[u][v])
							dis[v]=dis[u];
						else
							dis[v]=e[u][v];
					}
				}
			}
		} 
		printf("Scenario #%d:\n",k++);
		printf("%d\n",dis[n]);
		printf("\n");//
	}
	return 0;	
}