题解：Paid Roads（P3411）

一、题目分析

本题要求找到从城市1到城市N的最小花费路径，其中部分道路有两种付费方式：

1. 预付费：在城市$c_i$支付$P_i$
2. 后付费：在到达城市$b_i$后支付$R_i$（$P_i \leq R_i$）

关键约束：

• 城市编号1~N，道路数量1~10
• 状态需记录已访问城市（用于判断是否可预付费）
• 需处理重边和环

二、解题思路

1. 状态建模：
   使用Dijkstra算法，状态为$(u, mask)$，其中：

   • $u$：当前城市
   • $mask$：已访问城市的二进制掩码（第$i$位表示城市$i+1$是否访问过）

2. 预付费判断：
   若$mask$包含$c_i$，则可选择预付费$P_i$，否则只能后付费$R_i$。

3. 路径存在性检查：
   使用Floyd-Warshall算法预处理可达性矩阵，若城市1无法到达N则直接输出"impossible"。

三、代码解析

#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<queue>
using namespace std;
const int INF=(1<<29);

// 边结构：from->to，sit为预付费城市，dis1为预付费，dis2为后付费
struct edge {
    int from, to, sit, dis1, dis2;
};

// 优先队列节点：距离、当前城市、访问掩码
struct heapnode {
    int di, num1, num2;
    bool operator< (const heapnode j) const {
        return di > j.di;
    }
};

edge e[15];
int d[15][1100];     // 最小距离：d[u][mask]
int con[15][15];     // 可达性矩阵
int use[15][1100];   // 访问标记
int m, n;

void dijkstra(int s);
void floyd_warshall(void);

int main(void) {
    int i, j, u, p, ans;
    while(scanf("%d%d", &n, &m) == 2) {
        // 初始化可达性矩阵
        for(i = 1; i <= n; i++)
            for(j = 1; j <= n; j++)
                con[i][j] = (i == j) ? 1 : 0;
        
        // 读入边并更新可达性
        for(i = 1; i <= m; i++) {
            scanf("%d%d%d%d%d", &e[i].from, &e[i].to, &e[i].sit, &e[i].dis2, &e[i].dis1);
            con[e[i].from][e[i].to] = 1;
        }
        
        // 预处理可达性
        floyd_warshall();
        if(con[1][n] == 0) {
            printf("impossible\n");
        } else {
            // Dijkstra计算最短路径
            dijkstra(1);
            ans = INF;
            u = (1 << (n-1));
            p = (1 << n);
            // 遍历所有可能的终态
            for(j = 0; j < p; j++) {
                if(d[n][j|u|1] < ans)
                    ans = d[n][j|u|1];
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}

// Dijkstra算法：带状态的最短路径
void dijkstra(int s) {
    int i, j, u, v, p;
    heapnode h;
    priority_queue<heapnode> heap;
    p = (1 << n);
    
    // 初始化距离数组和访问标记
    for(i = 1; i <= n; i++)
        for(j = 0; j < p; j++) {
            d[i][j] = INF;
            use[i][j] = 0;
        }
    
    // 起点状态：距离0，城市s，掩码为仅包含s
    h.di = 0;
    h.num1 = s;
    h.num2 = (1 << (s-1));
    d[s][1 << (s-1)] = 0;
    heap.push(h);
    
    while(!heap.empty()) {
        h = heap.top();
        heap.pop();
        u = h.num1;
        v = h.num2;
        
        if(!use[u][v]) {
            use[u][v] = 1;
            // 遍历所有边
            for(i = 1; i <= m; i++) {
                if(e[i].from == u) {
                    // 情况1：未访问预付费城市，只能后付费
                    if((((1 << (e[i].sit-1)) & v) == 0) && 
                       (d[u][v] + e[i].dis1 < d[e[i].to][v | (1 << (e[i].to-1))])) {
                        d[e[i].to][v | (1 << (e[i].to-1))] = d[u][v] + e[i].dis1;
                        h.di = d[u][v] + e[i].dis1;
                        h.num1 = e[i].to;
                        h.num2 = (v | (1 << (e[i].to-1)));
                        heap.push(h);
                    }
                    // 情况2：已访问预付费城市，可选择预付费
                    else if((((1 << (e[i].sit-1)) & v) != 0) && 
                            (d[u][v] + e[i].dis2 < d[e[i].to][v | (1 << (e[i].to-1))])) {
                        d[e[i].to][v | (1 << (e[i].to-1))] = d[u][v] + e[i].dis2;
                        h.di = d[u][v] + e[i].dis2;
                        h.num1 = e[i].to;
                        h.num2 = (v | (1 << (e[i].to-1)));
                        heap.push(h);
                    }
                }
            }
        }
    }
}

// Floyd-Warshall算法：预处理可达性矩阵
void floyd_warshall(void) {
    int i, j, k;
    for(k = 1; k <= n; k++)
        for(i = 1; i <= n; i++)
            for(j = 1; j <= n; j++)
                con[i][j] = con[i][j] || (con[i][k] && con[k][j]);
}

四、关键步骤解析

1. 可达性预处理
   使用Floyd-Warshall算法计算所有城市对的可达性矩阵$con$，判断是否存在从1到N的路径。

2. 状态初始化

   • $d[u][mask]$：到达城市$u$且已访问城市集合为$mask$的最小花费
   • 初始状态：$d[1][1<<0] = 0$，其余为$INF$

3. 优先队列扩展
   每次从堆中取出当前距离最小的状态$(u, mask)$，扩展所有出边：

   • 预付费条件：若$mask$包含$c_i$，可选择$P_i$
   • 后付费条件：否则只能选择$R_i$
   • 更新新状态$(v, mask \cup \{v\})$的距离

4. 结果收集
   遍历所有可能的终态$d[N][mask]$（要求$mask$包含1和N），取最小值。

五、示例解析

对于输入：

4 5
1 2 1 10 10
2 3 1 30 50
3 4 3 80 80
2 1 2 10 10
1 3 2 10 50

1. 路径分析
   最优路径为：1 → 2 → 3 → 4

   • 1→2：预付费10（在1已访问）
   • 2→3：预付费30（在1已访问）
   • 3→4：预付费80（在3已访问）
     总花费：10 + 30 + 80 = 110

2. 状态转移

   • 初始：$(1, \{1\}, 0)$
   • 扩展到2：$(2, \{1,2\}, 10)$
   • 扩展到3：$(3, \{1,2,3\}, 40)$
   • 扩展到4：$(4, \{1,2,3,4\}, 120)$
     但存在更优路径，最终答案为110。

六、注意事项

1. 位运算处理

   • $mask$的第$i$位表示城市$i+1$是否访问（从0开始）
   • 更新掩码：$mask | (1 << (v-1))$

2. 状态空间

   • 城市数$n \leq 10$，状态数为$O(n \times 2^n) = 10 \times 1024$，可接受

3. 优先队列优化
   使用Dijkstra算法而非Bellman-Ford，避免重复扩展无效状态

七、复杂度分析

• 时间复杂度：$O(m \times n \times 2^n \log(n \times 2^n))$

  • Floyd-Warshall预处理：$O(n^3)$
  • Dijkstra状态扩展：$O(m \times n \times 2^n \log(n \times 2^n))$

• 空间复杂度：$O(n \times 2^n)$（距离数组和优先队列）

八、可能的优化

1. 双向Dijkstra
   从起点和终点同时搜索，可能减少状态扩展数。

2. 状态剪枝
   若发现某些状态不可能最优，提前剪枝。

3. 预处理优化
   对每个城市预处理可使用的预付费道路集合，减少状态转移时的判断。