题目分析

此程序借助广度优先搜索（BFS）算法来解决一个关于货物价值计算与选择的问题。具体而言，输入包含多个货物信息，每个货物有其初始价值，并且货物之间存在关联关系。程序会计算从一个特定节点（用 $*$ 表示）到各个货物节点的最短路径，同时依据路径长度对货物价值进行折扣计算，最终输出价值最高的货物。

输入输出要求

• 输入：输入包含多组数据，每组数据以一个整数 $n$ 开头，代表货物的数量。接着是 $n$ 行，每行包含三个部分：货物的名称（一个大写字母）、货物的初始价值（浮点数）以及与该货物相关联的其他货物名称（一串大写字母，若包含 $*$ 则表示与特定节点相关联）。当输入结束时，程序会停止。
• 输出：针对每组输入数据，输出价值最高的货物名称，格式为 $Import from X$，其中 $X$ 是货物的名称（大写字母）。

代码思路

1. 数据输入：持续读取输入，直至文件结束。针对每组输入，先读取货物数量 $n$，接着读取每个货物的信息，包含名称、初始价值以及关联的其他货物名称。
2. 图的构建：运用邻接矩阵 $g$ 来表示货物之间的关联关系，同时使用 $value$ 数组存储每个货物的初始价值。
3. 广度优先搜索（BFS）：以特定节点 $*$（编号为 26）作为起点，开展 BFS 以计算到各个货物节点的最短路径，将结果存储在 $dis$ 数组中。
4. 价值计算：依据最短路径长度，对每个货物的价值进行折扣计算。若最短路径长度大于 2，则每多一步价值乘以 0.95。
5. 结果输出：找出价值最高的货物，并输出其名称。

代码解释

#include <iostream>
#include <cstdio>
#include <string>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
// 存储每个货物的初始价值
double value[30];
// 存储从特定节点到每个货物节点的最短路径长度
int dis[30];
// 邻接矩阵，用于表示货物之间的关联关系
int g[100][100];
int main()
{
    while(1)
    {
        int n;
        cin>>n;    
        // 判断是否到达文件末尾，若是则结束程序
        if(cin.eof()==1)
        {
            break;
        }
        // 初始化邻接矩阵和最短路径长度数组
        memset(g,0,sizeof(g));
        memset(dis,-1,sizeof(dis));
        for(int i=0;i<n;i++)
        {
            string a,b;
            double d;
            cin>>a>>d>>b;
            // 获取货物的编号
            int from=a[0]-'A';
            value[from]=d;
            for(int i=0;i<b.size();i++)
            {
                int to;
                if(b[i]=='*')
                {
                    to=26;
                }else 
                {
                    to=b[i]-'A';
                }
                // 建立货物之间的关联关系
                g[from][to]=g[to][from]=1;
            }
        }
        // 使用队列进行 BFS
        queue<int> que;
        que.push(26);
        dis[26]=1;
        while(que.empty()!=1)
        {
            int t=que.front();
            que.pop();
            for(int i=0;i<=26;i++)
            {
                if(i!=t&& g[t][i]==1)
                {
                    if(dis[i]==-1 ||dis[i]>dis[t]+1)
                    {
                        // 更新最短路径长度
                        dis[i]=dis[t]+1;
                        que.push(i); 
                    }
                }
            }
        }
        double jg=-1;
        int jl=-1;
        for(int i=0;i<26;i++)
        {
            if(dis[i]!=-1)
            {
                if(dis[i]>2)
                {
                    int t=dis[i]-2;
                    while(t--)
                    {
                        // 根据最短路径长度对货物价值进行折扣计算
                        value[i]=value[i]*0.95;
                    }            
                }
                if(jg<value[i])
                {
                    // 找出价值最高的货物
                    jg=value[i];
                    jl=i;
                }                
            }
        }
        // 输出价值最高的货物名称
        cout<<"Import from "<<(char)(jl+'A')<<endl;
    }     
    return 0;
}

复杂度分析

• 时间复杂度：$O(n^2)$，其中 $n$ 是货物的数量。主要的时间开销在于 BFS 和价值计算的过程。
• 空间复杂度：$O(n^2)$，主要用于存储邻接矩阵。