• 理想路径问题


    一 问题描述

    给定一个有 n 个节点,m 条边的无向图,每边都涂有1种颜色。求节点1到n的一条路径,使得经过的边数最少,在此前提前,经过边的颜色序列最小。可能有自环和重边。

    二 输入和输出

    1 输入

    输入共 m+1 行,第1行包括两个整数:m和n。之后的m行,每行都包含3个整数a、b、c,表示a和b之间有一条颜色为c的路径。

    2 输出

    输出共两行,第1行包含正整数k,表示节点1到n至少需要经过k条边。第2行包含k个由空格隔开的正整数,表示节点1到n经过的边的颜色。

    3 输入样例

    4 6

    1 2 1

    1 3 2

    3 4 3

    2 3 1

    2 4 4

    3 1 1

    4 输出样例

    2

    1 3

    节点1到4至少经过两条边:1 > 3,颜色为1(最后输入的那条边);3 > 4,颜色为3。

    三 分析

    本问题求解节点1到n的最短距离,在此前提下,色号序列最小。可以先求最短距离,然后考察色号。因为在从节点1出发的多条边中,并不知道哪条边是最短路径上的边,所以无法确定最小色号。

    四 算法设计

    1 从节点n反向广度优先遍历标高,节点1的高度正好为从节点1到n的最短距离。

    2 从节点1正向广度优先遍历,沿着高度减1的方向遍历,找色号小的点,如果多个色号都最小,则考察下一个色号哪个最小,直到节点n结束。

    五 图解分析

    1 根据输入样例创建图,然后节点n反向广度优先遍历标高,节点1的高度为2,即节点1到n的最短距离为2,输出2。

    2 从节点1正向广度优先遍历,沿着高度减1的方向遍历,找边商色号小的邻接点,节点1到2的色号为1,节点1到3的色号为1,节点1到3的另外一条道路色号为2,最小色号为1,输出1,。目前无法确定选择哪条边,因此将可能走的两个邻接点2和3入队并暂存。

    3 从节点2和节点3出发,沿着高度减1的方向遍历,找边上色号小的邻接点,节点2到4的色为4,节点3到4的色号为3,最小色号为3,输出3。

    六 代码

    1. package graph.uva1599;
    2. import java.util.LinkedList;
    3. import java.util.Queue;
    4. import java.util.Scanner;
    5. public class UVA1599 {
    6. static final int inf = 0x7fffffff;
    7. static final int N = 100000 + 5;
    8. static final int M = 200000 + 5;
    9. static int n;
    10. static int m;
    11. static int cnt;
    12. static boolean vis[];
    13. // 保存节点号
    14. static Queue<Integer> q1 = new LinkedList<>();
    15. // 保存色号
    16. static Queue<Integer> q2 = new LinkedList<>();
    17. // 保存色号最小的边关联的邻接点号
    18. static Queue<Integer> q3 = new LinkedList<>();
    19. static int head[];
    20. static int dis[] = new int[N];
    21. static Edge e[] = new Edge[M];
    22. static {
    23. for (int i = 0; i < e.length; i++) {
    24. e[i] = new Edge();
    25. }
    26. }
    27. // 添加一条边
    28. static void add(int u, int v, int c) {
    29. e[++cnt].to = v;
    30. e[cnt].c = c;
    31. e[cnt].next = head[u];
    32. head[u] = cnt;
    33. }
    34. // 逆向标高求最短距离
    35. static void bfs1() {
    36. int u, v;
    37. vis = new boolean[N];
    38. dis[n] = 0;
    39. q1.add(n);
    40. vis[n] = true;
    41. while (!q1.isEmpty()) {
    42. u = q1.peek();
    43. q1.poll();
    44. vis[u] = true;
    45. for (int i = head[u]; i > 0; i = e[i].next) {
    46. v = e[i].to;
    47. if (vis[v])
    48. continue;
    49. dis[v] = dis[u] + 1;
    50. q1.add(v);
    51. vis[v] = true;
    52. }
    53. }
    54. }
    55. // 正向求色号序列
    56. static void bfs2() {
    57. int u, v, minc, c;
    58. boolean first = true;
    59. vis = new boolean[N];
    60. vis[1] = true;
    61. // 1号结点所有邻接点
    62. for (int i = head[1]; i > 0; i = e[i].next)
    63. // 高度减1的邻接点
    64. if (dis[e[i].to] == dis[1] - 1) {
    65. q1.add(e[i].to);
    66. q2.add(e[i].c);
    67. }
    68. while (!q1.isEmpty()) {
    69. minc = inf;
    70. while (!q1.isEmpty()) {
    71. v = q1.peek();
    72. q1.poll();
    73. c = q2.peek();
    74. q2.poll();
    75. if (c < minc) {
    76. while (!q3.isEmpty()) // 发现更小队列清空
    77. q3.poll();
    78. minc = c;
    79. }
    80. if (c == minc)
    81. q3.add(v);
    82. }
    83. if (first)
    84. first = false;
    85. else
    86. System.out.print(" ");
    87. System.out.print(minc);
    88. while (!q3.isEmpty()) { // 所有等于最小色号的结点
    89. u = q3.peek();
    90. q3.poll();
    91. if (vis[u])
    92. continue;
    93. vis[u] = true;
    94. for (int i = head[u]; i > 0; i = e[i].next) { // 扩展每一个结点
    95. v = e[i].to;
    96. if (dis[v] == dis[u] - 1) {
    97. q1.add(v);
    98. q2.add(e[i].c);
    99. }
    100. }
    101. }
    102. }
    103. }
    104. public static void main(String[] args) {
    105. Scanner scanner = new Scanner(System.in);
    106. int u, v, c;
    107. while (true) {
    108. n = scanner.nextInt();
    109. m = scanner.nextInt();
    110. head = new int[N];
    111. for (int i = 0; i < head.length; i++) {
    112. head[i] = 0;
    113. }
    114. cnt = 0;
    115. for (int i = 1; i <= m; i++) {
    116. u = scanner.nextInt();
    117. v = scanner.nextInt();
    118. c = scanner.nextInt();
    119. add(u, v, c);
    120. add(v, u, c);
    121. }
    122. bfs1();
    123. System.out.println(dis[1]);
    124. bfs2();
    125. System.out.println();
    126. }
    127. }
    128. }
    129. class Edge {
    130. int to;
    131. int c;
    132. int next;
    133. }

    七 测试

    绿色为输入,白色为输出。

  • 相关阅读:
    使用ELK8.4.1环境+Filebeat收集nginx日志
    Linux平台如何实现采集音视频数据并注入轻量级RTSP服务?
    如何评价GPT-4o?
    数据库管理系统(DBMS)分类
    R语言使用aov函数执行单因素方差分析、使用TukeyHSD函数分析单因素方差分析的结果并解读TukeyHSD函数的输出结果
    系统启动流程
    CSS【进阶】
    欧姆龙PLC串口通讯详解
    如何在CentOS系统中管理Docker容器
    Java框架(三)--Spring IoC容器与Bean管理(2)--基于XML配置Bean
  • 原文地址:https://blog.csdn.net/chengqiuming/article/details/125467480