分析：

这是一个基于无向图的最短路径问题：

• 城市（仓库）作为图的节点
• 航线作为图的边（边权为 1，表示相邻）
• 需要计算每对城市之间的最少边数路径，并据此计算运输费用

算法核心原理

1.广度优先搜索（BFS）： 由于所有边权为 1，BFS 能在线性时间 O (V+E) 内找到最短路径,比 Floyd-Warshall 算法的 O (V³) 更高效，尤其适用于稀疏图

2.数据结构优化： 使用邻接表vector<vector>替代邻接矩阵，节省空间,通过map<string, int>实现城市名称到整数索引的映射

步骤

1.输入处理： 读取多个数据集，每个数据集包含城市、航线和请求 使用map建立城市名称到索引的映射，便于快速查找

2.图构建： 邻接表adj存储每个节点的邻居，每条航线对应无向图的两条边

3.BFS 实现： 初始化距离数组dist为无穷大，从起点开始 BFS，逐层扩展，首次到达目标节点时的距离即为最短路径

4.结果计算： 若路径存在，费用 = 货物尺寸 × 路径长度 × 100 若不可达，输出 "NO SHIPMENT POSSIBLE"

c++代码：

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <climits>
#include <string>
using namespace std;

void solve() {
    int datasets;
    cin >> datasets;
    
    cout << "SHIPPING ROUTES OUTPUT" << endl;
    
    for (int dataset = 1; dataset <= datasets; dataset++) {
        cout << endl << "DATA SET " << dataset << endl;
        
        int M, N, P;
        cin >> M >> N >> P;
        
        map<string, int> warehouse_index;
        vector<string> warehouses(M);
        
        for (int i = 0; i < M; i++) {
            cin >> warehouses[i];
            warehouse_index[warehouses[i]] = i;
        }
        
        // 修改1：在嵌套模板参数的>>间添加空格
        vector<vector<int> > adj(M);
        
        for (int i = 0; i < N; i++) {
            string a, b;
            cin >> a >> b;
            int u = warehouse_index[a];
            int v = warehouse_index[b];
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        
        for (int i = 0; i < P; i++) {
            int size;
            string start, end;
            cin >> size >> start >> end;
            
            if (warehouse_index.find(start) == warehouse_index.end() || 
                warehouse_index.find(end) == warehouse_index.end()) {
                cout << "NO SHIPMENT POSSIBLE" << endl;
                continue;
            }
            
            int s = warehouse_index[start];
            int e = warehouse_index[end];
            
            vector<int> dist(M, INT_MAX);
            dist[s] = 0;
            queue<int> q;
            q.push(s);
            
            while (!q.empty()) {
                int u = q.front();
                q.pop();
                
                // 修改2：若不启用C++11，改为传统for循环
                /* C++11写法（需编译参数支持）：
                for (int v : adj[u]) {
                    if (dist[v] == INT_MAX) {
                        dist[v] = dist[u] + 1;
                        q.push(v);
                    }
                }
                */
                
                // 传统for循环写法（兼容C++98）：
                for (int j = 0; j < adj[u].size(); j++) {
                    int v = adj[u][j];
                    if (dist[v] == INT_MAX) {
                        dist[v] = dist[u] + 1;
                        q.push(v);
                    }
                }
            }
            
            if (dist[e] != INT_MAX) {
                cout << "$" << size * dist[e] * 100 << endl;
            } else {
                cout << "NO SHIPMENT POSSIBLE" << endl;
            }
        }
    }
    
    cout << endl << "END OF OUTPUT" << endl;
}

int main() {
    solve();
    return 0;
}