吸血鬼旅行问题题解

一、题目分析

弗拉基米尔作为吸血鬼旅行需要满足以下条件：

• 只能在18:00-06:00（即18-30点，30点对应次日6点）之间旅行
• 每天中午12点需要饮用1升血
• 求从起点到终点的最短路线，使得携带的血量最少

关键点：

• 出发时间需≥18点，到达时间需≤30点
• 若跨天旅行，需计算所需血量
• 使用SPFA算法求解带时间状态的最短路径

二、算法思路

1. 状态定义：dis[i][j]表示在j点到达城市i所需的最少血量
2. 图模型：
   • 节点：城市
   • 边：火车路线，包含目标城市、出发时间、到达时间
3. 时间处理：
   • 18:00-06:00映射为18-30点（30点对应次日6点）
   • 出发时间<6点时转换为24+出发时间
4. 状态转移：
   • 若当前到达时间≤火车出发时间，同一天乘坐，血量不变
   • 若当前到达时间>火车出发时间，需跨天乘坐，血量+1
5. 求解方法：使用SPFA算法，枚举所有可能的到达时间状态

三、代码实现

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a; i < b; i++)
#define _rep(i,a,b) for(int i = a; i <= b; i++)
const int maxn = 107;
const int inf = 1e9;

// 定义边结构：目标城市、出发时间、到达时间
struct edge{
    int to, st, end_time;
    edge(int _to,int _st,int _end_time): to(_to), st(_st), end_time(_end_time){}
};

// 定义队列节点：到达城市、到达时间
struct node{
    int to, arr_time;
    node(int _to, int _arr_time): to(_to), arr_time(_arr_time){}
};

vector<edge> G[maxn];  // 邻接表存储图
map<string, int> id;   // 城市名称到数字的映射
int city_cnt, m;       // 城市数量、路线数量

// 初始化图和映射
void init(){
    for(int i = 0; i < maxn; i++) G[i].clear();
    id.clear();
    city_cnt = 0;
}

// 将城市名称映射为数字ID
void s2i(string s){
    if(!id.count(s)) id[s] = city_cnt++;
}

// SPFA算法求解最少血量
int spfa(int from, int to){
    int dis[maxn][37];  // dis[i][j]表示在j点到达城市i所需的最少血量
    bool vis[maxn][37]; // 标记状态是否在队列中
    
    // 初始化距离数组为无穷大
    rep(i,0,city_cnt) _rep(j,18,36) dis[i][j] = inf;
    memset(vis, 0, sizeof(vis));
    
    queue<node> q;
    // 初始状态：起点在18-30点到达时血量为0
    _rep(i,18,30){
        vis[from][i] = 1;
        dis[from][i] = 0;
        q.push(node(from, i));
    }
    
    while(!q.empty()){
        node f = q.front();
        int u = f.to, t = f.arr_time;
        q.pop();
        vis[u][t] = 0;  // 出队时取消标记
        
        // 遍历所有从u出发的路线
        rep(i,0,G[u].size()){
            int st_time = G[u][i].st;  // 路线出发时间
            int v = G[u][i].to;       // 目标城市
            int ed_time = G[u][i].end_time;  // 路线到达时间
            
            if(t <= st_time){
                // 同一天可以赶上火车，血量不变
                if(dis[v][ed_time] > dis[u][t]){
                    dis[v][ed_time] = dis[u][t];
                    if(!vis[v][ed_time]){
                        vis[v][ed_time] = 1;
                        q.push(node(v, ed_time));
                    }
                }
            } else {
                // 需跨天乘坐，血量+1
                if(dis[v][ed_time] > dis[u][t] + 1){
                    dis[v][ed_time] = dis[u][t] + 1;
                    if(!vis[v][ed_time]){
                        vis[v][ed_time] = 1;
                        q.push(node(v, ed_time));
                    }
                }
            }
        }
    }
    
    // 枚举终点在18-30点到达时的最少血量
    int min_dis = inf;
    _rep(i,18,30) min_dis = min(min_dis, dis[to][i]);
    return min_dis;
}

int main(){
    int T, kase = 1;
    cin >> T;
    while(T--){
        init();
        string from, to;
        cin >> m;
        
        // 读取并处理每条路线
        rep(i,0,m){
            string u, v;
            int st, dur;
            cin >> u >> v >> st >> dur;
            s2i(u), s2i(v);
            
            // 处理出发时间：小于6点转换为24+st
            if(st <= 6) st += 24;
            
            // 检查路线是否合法：出发时间≥18且到达时间≤30
            if(st >= 18 && st + dur <= 30){
                G[id[u]].push_back(edge(id[v], st, st + dur));
            }
        }
        
        // 读取起点和终点
        cin >> from >> to;
        s2i(from), s2i(to);
        
        cout << "Test Case " << kase++ << ".\n";
        int blood = spfa(id[from], id[to]);
        
        if(blood == inf)
            cout << "There is no route Vladimir can take.\n";
        else
            cout << "Vladimir needs " << blood << " litre(s) of blood.\n";
    }
    return 0;
}

四、代码解释

1. 输入处理：

   • 将城市名称映射为数字ID便于处理
   • 转换出发时间：小于6点的转换为24+出发时间
   • 过滤不合法路线：出发时间<18或到达时间>30的路线被忽略

2. SPFA算法核心：

   • 状态定义：dis[i][j]表示在j点到达城市i的最少血量
   • 初始状态：起点在18-30点到达时血量为0
   • 状态转移：
     • 同一天乘坐火车：血量不变
     • 跨天乘坐火车：血量+1
   • 队列维护：使用vis数组避免重复入队

3. 结果计算：

   • 枚举终点在18-30点到达时的所有状态，取最小血量
   • 若最小血量仍为无穷大，说明没有可行路线

五、复杂度分析

• 时间复杂度：O(M×T)，其中M为路线数，T为时间状态数（18-30共13个时间点）
• 空间复杂度：O(N×T)，N为城市数，T为时间状态数
• 该算法在题目给定的约束下（城市数≤100，路线数<1000）能够高效运行

六、示例解析

以第二个测试用例为例：

1. 路线处理后，Lugoj到Bacau的可行路线需要经过中转
2. SPFA算法会找到一条需要2天的路线，因此需要携带2升血
3. 最终输出"Vladimir needs 2 litre(s) of blood."

该算法通过状态压缩和SPFA算法，有效解决了带时间约束的最短路径问题，确保在合法时间内找到所需血量最少的路线。