public class MultiConditionFloyd { // 定义最大安全值（避免溢出） static final int INF = 0x3f3f3f3f; // n个节点 int n; // ========== 多条件DP数组 ========== // 第一维：最优值（如最短距离） long[][] dist; // 第二维：次优条件（如最小费用、最少边数等） long[][] cost; // 或 int[][] edgeCount; // 第三维：路径计数（最优路径有多少条） long[][] count; // 路径记录（可选） int[][] next; // 用于路径还原 public MultiConditionFloyd(int n) { this.n = n; dist = new long[n][n]; cost = new long[n][n]; count = new long[n][n]; next = new int[n][n]; // 初始化 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dist[i][j] = (i == j) ? 0 : INF; cost[i][j] = (i == j) ? 0 : INF; count[i][j] = (i == j) ? 1 : 0; // 自身到自身算1条路径 next[i][j] = j; } } } // 添加边（根据题目要求处理重边） public void addEdge(int u, int v, long d, long c) { // 如果距离相同，取更优的次条件 if (d < dist[u][v]) { dist[u][v] = d; cost[u][v] = c; count[u][v] = 1; } else if (d == dist[u][v]) { // 距离相同，比较第二条件 if (c < cost[u][v]) { cost[u][v] = c; count[u][v] = 1; } else if (c == cost[u][v]) { // 两个条件都相同，路径数累加 count[u][v]++; } } } // 核心：多条件弗洛伊德 public void run() { for (int k = 0; k < n; k++) {//k在最外面 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (dist[i][k] == INF || dist[k][j] == INF) continue; long newDist = dist[i][k] + dist[k][j]; long newCost = cost[i][k] + cost[k][j]; // ========== 多条件比较逻辑 ========== if (newDist < dist[i][j]) { // 找到更短路径，全面更新 dist[i][j] = newDist; cost[i][j] = newCost; count[i][j] = count[i][k] * count[k][j]; // 乘法原理 next[i][j] = next[i][k]; } else if (newDist == dist[i][j]) { // 距离相等，进入第二条件比较 if (newCost < cost[i][j]) { // 距离相同但费用更少 cost[i][j] = newCost; count[i][j] = count[i][k] * count[k][j]; next[i][j] = next[i][k]; } else if (newCost == cost[i][j]) { // 两个条件都相同，累加路径数 count[i][j] += count[i][k] * count[k][j]; // 注意：可能需要取模 count[i][j] %= MOD; } } } } } } // 获取路径（利用next数组） public List<Integer> getPath(int start, int end) { List<Integer> path = new ArrayList<>(); if (dist[start][end] == INF) return path; int cur = start; path.add(cur); while (cur != end) { cur = next[cur][end]; path.add(cur); } return path; } }
