题目描述

给定一个包含 $N$ 个城市和 $M$ 条双向道路的地图。每条道路连接两个城市，并具有两个属性：一个是“旅费”（cost），另一个是“途径风景心情指数”（fun index）。银行卡有一个消费额度 $b$。

旅行规则是：从一个城市出发，前往任何其他城市都必须选择旅费最低的路线。

我们需要处理 $k$ 次咨询。对于每次咨询给定的出发城市 start_city：
1. 找出所有可以从 start_city 出发到达的目标城市 dest_city，条件是：从 start_city 到 dest_city 的最低旅费不超过银行卡额度 $b$。
2. 在所有满足条件 1 的目标城市中，找出那些通过最低旅费路线到达时，路线上的心情指数总和达到最大的城市。注意，可能有多条不同的路线都具有相同的最低旅费，我们需要考虑这些路线中能达到的最大心情指数总和。

对于每次咨询，需要输出两行：
第一行：所有满足条件 1 的目标城市编号（按升序排列）。
第二行：所有满足条件 2 的目标城市编号（按升序排列）。
* 如果没有任何城市满足条件 1（即无法在额度内去任何其他地方），则第二行输出 T_T。

样例

输入:
500 8 11 3
1 2 400 20
2 3 100 50
1 4 1000 90
1 5 300 10
4 5 200 60
2 5 100 10
3 5 500 80
5 6 200 20
6 7 500 70
3 7 300 10
7 8 800 100
1 8 7

输出:
2 3 4 5 6
3 4
T_T
2 3 5 6
5 6

算法 (Floyd-Warshall)

$O(N^3)$

思路分析

核心问题在于，对于任意两个城市 $(i, j)$，我们需要知道它们之间的最低旅费，以及在所有最低旅费路径中能达到的最大心情指数总和。这是一个典型的所有顶点对最短路径问题，并且需要在计算最短路径（最低旅费）的同时，维护一个次要属性（最大心情指数）。Floyd-Warshall 算法非常适合解决这类问题。

1. 状态定义:

   • cost[i][j]：存储从城市 $i$ 到城市 $j$ 的当前已知的最低旅费。
   • f[i][j]：存储从城市 $i$ 到城市 $j$ 的、对应于当前最低旅费 cost[i][j] 的路径中，可以达到的最大心情指数总和。

2. 初始化:

   • 将所有 cost[i][j] 初始化为一个非常大的值（例如 1E9），表示初始时城市间不直接连通（除非 $i=j$）。
   • 将所有 cost[i][i] 初始化为 0，表示从一个城市到自身不需要旅费。
   • 将所有 f[i][j] 初始化为 0。f[i][i] 始终为 0。
   • 读取 $M$ 条道路信息 (u, v, w0, w1)，其中 w0 是旅费，w1 是心情指数。城市编号需要转换为 0-based 索引（例如，u--, v--）。
   • 对于每条直接道路 $(u, v)$：
     • 更新最低旅费：cost[u][v] = min(cost[u][v], w0) 和 cost[v][u] = min(cost[v][u], w0)。这处理了可能存在的多条直达道路，只保留旅费最低的那条。
     • 更新心情指数：我们需要让 f[u][v] 存储与 cost[u][v] 对应的这条最低旅费直达路径的心情指数。代码中使用了 f[u][v] = max(f[u][v], w1) 和 f[v][u] = max(f[v][u], w1)。这看起来是取了所有直达路径中最大的心情指数。但结合 Floyd-Warshall 的更新逻辑，这种初始化方式最终是正确的。因为如果存在多条成本相同的最低价直达路径，我们确实希望记录其中心情指数最高的那条作为初始值。如果之后发现通过中转点可以获得更低的成本，f[i][j] 会被重置；如果发现通过中转点可以获得相同最低成本但更高的心情指数，f[i][j] 也会被更新为更高的值。

3. Floyd-Warshall 核心逻辑:
   算法通过考虑中间节点 $k$ 来逐步放松（优化）所有顶点对 $(i, j)$ 之间的路径。
   for k from 0 to n-1: for i from 0 to n-1: for j from 0 to n-1: // 尝试通过节点 k 更新从 i 到 j 的路径
   在内层循环中，比较直接从 $i$ 到 $j$ 的当前最优路径 (cost[i][j], f[i][j]) 与通过中间节点 $k$ 的路径 (cost[i][k] + cost[k][j], f[i][k] + f[k][j])。

   • 情况 1：找到更短（旅费更低）的路径
     如果 cost[i][j] > cost[i][k] + cost[k][j]，说明通过 $k$ 的路径旅费更低。

     • 更新最低旅费：cost[i][j] = cost[i][k] + cost[k][j]。
     • 重置最大心情指数：因为找到了新的、唯一的最低旅费路径，这条路径的心情指数总和就是 f[i][k] + f[k][j]。所以，f[i][j] = f[i][k] + f[k][j]。

   • 情况 2：找到旅费相同的路径
     如果 cost[i][j] == cost[i][k] + cost[k][j]，说明通过 $k$ 的路径与当前已知的最低旅费路径具有相同的旅费。这时，我们关心哪条路径的心情指数总和更高。

     • 旅费 cost[i][j] 不变。
     • 更新最大心情指数：取当前记录的最大心情指数 f[i][j] 和通过 $k$ 的路径的心情指数 f[i][k] + f[k][j] 中的较大者。f[i][j] = max(f[i][j], f[i][k] + f[k][j])。

   • 情况 3：通过 $k$ 的路径旅费更高
     如果 cost[i][j] < cost[i][k] + cost[k][j]，则通过 $k$ 的路径不是更优的选择，cost[i][j] 和 f[i][j] 保持不变。

   注意：代码中的 if (i != j && j != k && i != k) 条件是不必要的，可以移除。标准的 Floyd-Warshall 算法不需要这个检查。

4. 处理咨询:
   在 Floyd-Warshall 算法执行完毕后，cost[i][j] 存储了 $i$ 到 $j$ 的最低旅费，f[i][j] 存储了对应最低旅费路径的最大心情指数总和。
   对于每个咨询的出发城市 x (0-based)：

   • 遍历所有可能的目的地城市 i (从 0 到 n-1)。
   • 如果 i != x 且 cost[x][i] <= b（目的地不是出发点本身，且旅费在额度内），则城市 i 是可达的。将 i 加入列表 ans0。
   • 在遍历可达城市 i 的同时，维护当前找到的最大心情指数 mx 和对应的城市列表 ans1。
     • 如果 f[x][i] > mx，说明找到了一个心情指数更高的最低旅费路径。更新 mx = f[x][i]，并清空 ans1，将 i 加入 ans1。
     • 如果 f[x][i] == mx，说明找到了另一个具有相同最大心情指数的最低旅费路径目的地。将 i 加入 ans1。
   • 遍历结束后，ans0 包含了所有额度内可达的城市，ans1 包含了其中心情指数最高的城市。

5. 输出:

   • 按升序输出 ans0 中的城市编号（记得加 1 转换回 1-based）。
   • 如果 ans1 为空（即 ans0 也为空，没有任何城市可达），输出 T_T。
   • 否则，按升序输出 ans1 中的城市编号（记得加 1）。

时间复杂度

• 初始化邻接矩阵：$O(N^2)$。
• 读取道路信息：$O(M)$。
• Floyd-Warshall 算法：$O(N^3)$。
• 处理 $k$ 次咨询：每次咨询需要遍历 $N$ 个潜在目的地，复杂度为 $O(N)$。总共 $O(k \times N)$。
• 输出结果：最坏情况下，每次咨询输出 $O(N)$ 个城市。总共 $O(k \times N)$。

整体时间复杂度由 Floyd-Warshall 算法主导，为 $O(N^3)$。

空间复杂度

• cost 矩阵：$O(N^2)$。
• f 矩阵：$O(N^2)$。
• 其他辅助变量：$O(N)$。

整体空间复杂度为 $O(N^2)$。

C++ 代码

#include "bits/stdc++.h" // 引入所有标准库

using namespace std;
using i64 = long long;

constexpr int N = 500; // 最大城市数
// cost[i][j]: 城市 i 到 j 的最低旅费
// f[i][j]: 城市 i 到 j 的最低旅费路径对应的最大心情指数总和
int cost[N + 1][N + 1], f[N + 1][N + 1];

int main() {
    // 关闭 C++ 标准 IO 流与 C stdio 的同步，提高 cin/cout 速度
    ios::sync_with_stdio(false);
    // 解除 cin 和 cout 的绑定，进一步提速
    cin.tie(nullptr);

    int b, n, m, k; // b:额度, n:城市数, m:道路数, k:咨询数
    cin >> b >> n >> m >> k;

    // --- 初始化 cost 和 f 矩阵 ---
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // 初始化旅费为无穷大 (一个足够大的数)
            cost[i][j] = 1E9;
            // f 初始化为 0 (全局/静态数组默认初始化为0)
        }
        // 到自身的旅费为 0
        cost[i][i] = 0;
    }

    // --- 读取道路信息并更新初始 cost 和 f ---
    for (int i = 0; i < m; i++) {
        int u, v, w0, w1; // 城市1, 城市2, 旅费, 心情指数
        cin >> u >> v >> w0 >> w1;

        u--, v--; // 转换为 0-based 索引

        // 更新 u 到 v 的直达路径
        if (w0 < cost[u][v]) { // 如果找到更便宜的直达路
            cost[u][v] = w0;
            f[u][v] = w1; // 更新成本和对应的心情指数
        } else if (w0 == cost[u][v]) { // 如果找到同样便宜的直达路
            f[u][v] = max(f[u][v], w1); // 更新为较大的心情指数
        }
        // 更新 v 到 u 的直达路径 (因为是双向道路)
        if (w0 < cost[v][u]) {
            cost[v][u] = w0;
            f[v][u] = w1;
        } else if (w0 == cost[v][u]) {
            f[v][u] = max(f[v][u], w1);
        }
    }

    // --- Floyd-Warshall 算法 ---
    // k 是中间节点
    for (int kk = 0; kk < n; kk++) {
        // i 是起点
        for (int i = 0; i < n; i++) {
            // j 是终点
            for (int j = 0; j < n; j++) {
                // 尝试通过节点 kk 更新 i 到 j 的路径
                // if (i != j && j != kk && i != kk) { // 这个条件是不必要的，已注释
                    // 计算通过 kk 的路径成本和心情指数
                    int new_cost = cost[i][kk] + cost[kk][j];
                    int new_f = f[i][kk] + f[kk][j];

                    // 如果通过 kk 的成本更低
                    if (cost[i][j] > new_cost) {
                        cost[i][j] = new_cost; // 更新最低成本
                        f[i][j] = new_f;     // 重置最大心情指数
                    } 
                    // 如果通过 kk 的成本相同
                    else if (cost[i][j] == new_cost) {
                        // 更新最大心情指数为两者中的较大值
                        f[i][j] = max(f[i][j], new_f);
                    }
                // }
            }
        }
    }

    // --- 处理 k 次咨询 ---
    while (k--) {
        int x; // 咨询的出发城市编号 (1-based)
        cin >> x;
        x--; // 转换为 0-based 索引

        vector<int> ans0; // 存储额度内可达城市
        vector<int> ans1; // 存储其中心情指数最高的城市
        int mx = -1; // 当前找到的最大心情指数 (初始化为-1，因为心情指数非负)

        // 遍历所有可能的目的地城市 i
        for (int i = 0; i < n; i++) {
            // 如果目的地不是出发点本身，且旅费在额度内
            if (i != x && cost[x][i] <= b) {
                ans0.push_back(i); // 将城市 i 加入可达列表

                // 比较心情指数 f[x][i] 与当前最大值 mx
                if (f[x][i] > mx) { // 找到更高的心情指数
                    mx = f[x][i]; // 更新最大值
                    ans1.clear(); // 清空之前的最高列表
                    ans1.push_back(i); // 加入新的最高城市
                } else if (f[x][i] == mx) { // 找到相同的心情指数
                    ans1.push_back(i); // 加入列表
                }
            }
        }

        // --- 输出结果 ---
        // 输出第一行：所有可达城市
        // C++20 可以用 ranges::views::transform 和 ranges::copy
        // 这里用传统循环输出
        bool first_city = true;
        for (int city_idx : ans0) {
            if (!first_city) {
                cout << " ";
            }
            cout << city_idx + 1; // 输出 1-based 编号
            first_city = false;
        }
        cout << "\n"; // 换行

        // 输出第二行：心情指数最高的城市
        if (ans1.empty()) { // 如果没有可达城市 (ans0 为空，则 ans1 也为空)
            cout << "T_T\n";
        } else {
            first_city = true;
            for (int city_idx : ans1) {
                 if (!first_city) {
                    cout << " ";
                 }
                 cout << city_idx + 1; // 输出 1-based 编号
                 first_city = false;
            }
            cout << "\n"; 
        }
    }

    return 0; // 程序正常结束
}