当前位置：首页 > news >正文

UVa 383 Shipping Routes

news 2026/6/4 21:32:50

题目描述

Slow Boat to China\texttt{Slow Boat to China}Slow Boat to China航运公司需要一个程序来帮助快速向潜在客户报价。运费取决于货物的大小和所需的运输段数。一个运输段连接两个仓库，但并非所有仓库之间都有直接连接，因此从一个仓库到另一个仓库可能需要多个运输段。

每个数据集包含111到303030个仓库。每个仓库由两个大写字母标识。运输段是双向的，存在于任意两个不同的仓库之间。

运费 = 货物大小 × 所需运输段数 ×100100100。

对于给定的运输请求（货物大小、始发仓库、目的仓库），程序输出最佳（最便宜）的运费，如果无法运输则输出相应信息。

输入格式

第一行包含整数TTT（1≤T≤101 \leq T \leq 101≤T≤10），表示数据集中数据集的个数。

每个数据集的第一行包含三个整数：

MMM（1≤M≤301 \leq M \leq 301≤M≤30）：仓库数量
NNN（0≤N≤M(M−1)/20 \leq N \leq M(M-1)/20≤N≤M(M−1)/2）：运输段数量
PPP（0≤P≤100 \leq P \leq 100≤P≤10）：运输请求数量

第二行包含MMM个两个字母的仓库代码（大写字母），以空格分隔。

接下来NNN行，每行包含两个仓库代码，表示它们之间有直接运输段。

接下来PPP行，每行包含一个整数（货物大小）和两个仓库代码（始发地和目的地）。

输出格式

第一行输出SHIPPING ROUTES OUTPUT。对于每个数据集，输出DATA SET X标题，然后PPP行结果（$cost或NO SHIPMENT POSSIBLE）。最后一行输出END OF OUTPUT。

样例输入

2 6 7 5 AA CC QR FF DD AB AA CC CC QR DD CC AA DD AA AB DD QR AB DD 5 AA AB 14 DD CC 1 CC DD 2 AA FF 13 AB QR 3 0 1 AA BB CC 5 AA CC

样例输出

SHIPPING ROUTES OUTPUT DATA SET 1 $500 $1400 $100 NO SHIPMENT POSSIBLE $2600 DATA SET 2 NO SHIPMENT POSSIBLE END OF OUTPUT

题目分析

问题的本质

这是一个图论最短路径问题。每个仓库是节点，运输段是边（权重为111）。需要回答多个查询：给定起点和终点，求最短路径长度（运输段数），然后计算运费。

算法选择

节点数M≤30M \leq 30M≤30，可以使用Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法计算所有点对之间的最短路径
时间复杂度O(M3)=27000O(M^3) = 27000O(M3)=27000，完全可行
或对每个查询使用BFS\texttt{BFS}BFS，但P≤10P \leq 10P≤10，MMM很小，两种方法均可

无连接处理

如果两点之间不可达，距离为无穷大，输出NO SHIPMENT POSSIBLE。

运费计算

运费 = 货物大小 × 最短路径长度 ×100100100。

参考代码

// Shippint Routes// UVa ID: 383// Verdict: Accepted// Submission Date: 2016-06-28// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMAX_LEGS=100000;// 无穷大intmain(intargc,char*argv[]){intdatasets=0,cases=0;cin>>datasets;cout<<"SHIPPING ROUTES OUTPUT"<<endl<<endl;while(datasets--){intM,N,P;cin>>M>>N>>P;// 仓库代码到索引的映射map<string,int>warehouses;for(inti=1;i<=M;i++){string codes;cin>>codes;warehouses[codes]=i;}// 初始化距离矩阵intlegs[M+1][M+1];for(inti=1;i<=M;i++){for(intj=1;j<=M;j++)legs[i][j]=MAX_LEGS;legs[i][i]=0;}// 读取边（运输段）for(inti=1;i<=N;i++){string start,next;cin>>start>>next;legs[warehouses[start]][warehouses[next]]=1;legs[warehouses[next]][warehouses[start]]=1;}// Floyd-Warshall 计算所有点对最短路径for(intk=1;k<=M;k++)for(inti=1;i<=M;i++)for(intj=1;j<=M;j++)if(legs[i][k]+legs[k][j]<legs[i][j])legs[i][j]=legs[i][k]+legs[k][j];cout<<"DATA SET "<<++cases<<endl<<endl;// 处理查询for(inti=1;i<=P;i++){intsize;string start,next;cin>>size>>start>>next;intdist=legs[warehouses[start]][warehouses[next]];if(dist>=MAX_LEGS){cout<<"NO SHIPMENT POSSIBLE"<<endl;continue;}cout<<"$"<<size*dist*100<<endl;}cout<<endl;}cout<<"END OF OUTPUT"<<endl;return0;}