输入输出样例

样例1

输入

  1. 5 10
  2. 1 2
  3. 1 3
  4. 1 4
  5. 1 5
  6. 2 3
  7. 2 4
  8. 2 5
  9. 3 4
  10. 3 5
  11. 4 5
  12. 1 27
  13. 1 1 1
  14. 2 1 2
  15. 3 1 3
  16. 4 1 4
  17. 5 1 5
  18. 1 1
  19. 2 1
  20. 3 1
  21. 4 1
  22. 5 1
  23. 1 2
  24. 2 2
  25. 3 2
  26. 4 2
  27. 5 2
  28. 1 10 10
  29. 2 11 9
  30. 1 11
  31. 2 11
  32. 3 11
  33. 4 11
  34. 5 11
  35. 1 12
  36. 2 12
  37. 3 12
  38. 4 12
  39. 5 12

输出

  1. 2 0 1
  2. 2 0 2
  3. 2 0 3
  4. 2 0 4
  5. 2 0 5
  6. 2 0 1
  7. 2 0 1
  8. 2 0 1
  9. 2 0 1
  10. 2 0 1
  11. 3 0 1 10
  12. 4 0 1 10 9
  13. 3 0 1 10
  14. 3 0 1 10
  15. 3 0 1 10
  16. 4 0 1 10 9
  17. 4 0 1 10 9
  18. 4 0 1 10 9
  19. 4 0 1 10 9
  20. 4 0 1 10 9

样例2

输入

  1. 15 13
  2. 1 2
  3. 2 3
  4. 3 4
  5. 4 5
  6. 1 6
  7. 6 7
  8. 7 8
  9. 8 9
  10. 1 10
  11. 10 11
  12. 11 12
  13. 12 13
  14. 14 15
  15. 6 28
  16. 1 1 1
  17. 1 2 2
  18. 1 6
  19. 2 7
  20. 13 7
  21. 9 7
  22. 5 7
  23. 3 14
  24. 8 14
  25. 5 14
  26. 11 14
  27. 9 25
  28. 5 25
  29. 13 25
  30. 9 29 3
  31. 5 29 4
  32. 13 29 5
  33. 1 53
  34. 2 59 6
  35. 2 59
  36. 1 1000
  37. 3 1000
  38. 8 1000
  39. 9 1000
  40. 10 1000
  41. 13 1000
  42. 14 1000
  43. 15 1000

输出

  1. 3 0 1 2
  2. 2 0 1
  3. 1 0
  4. 1 0
  5. 1 0
  6. 3 0 1 2
  7. 1 0
  8. 1 0
  9. 3 0 1 2
  10. 2 0 1
  11. 2 0 1
  12. 2 0 1
  13. 4 0 1 2 3
  14. 5 0 1 2 3 6
  15. 5 0 1 2 3 6
  16. 5 0 1 2 3 6
  17. 5 0 1 2 3 6
  18. 5 0 1 2 3 6
  19. 5 0 1 2 3 6
  20. 5 0 1 2 3 6
  21. 1 0
  22. 1 0

题解一

BFS模拟。80分。
参考：https://www.mscto.com/blockchain/238982.html

  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.ArrayList;
  5. import java.util.LinkedList;
  6. import java.util.List;
  7. import java.util.Queue;
  9. public class Main {
  11.     public static void main(String[] args) throws IOException {
  12.         BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  13.         String[] strs = reader.readLine().split(" ");
  14.         int n = Integer.parseInt(strs[0]);
  15.         int m = Integer.parseInt(strs[1]);
  16.         Node[] nodes = new Node[n + 1];
  17.         for (int i = 0; i <= n; ++i) {
  18.             nodes[i] = new Node(n, i);
  19.         }
  20.         for (int i = 0, u, v; i < m; ++i) {
  21.             strs = reader.readLine().split(" ");
  22.             u = Integer.parseInt(strs[0]);
  23.             v = Integer.parseInt(strs[1]);
  24.             nodes[u].partners.add(nodes[v]);
  25.             nodes[v].partners.add(nodes[u]);
  26.         }
  28.         strs = reader.readLine().split(" ");
  29.         int t = Integer.parseInt(strs[0]);
  30.         int k = Integer.parseInt(strs[1]);
  32.         // 更新消息队列
  33.         Queue<Message> queue = new LinkedList<>();
  34.         for (int i = 0, a, b, c; i < k; ++i) {
  35.             strs = reader.readLine().split(" ");
  36.             a = Integer.parseInt(strs[0]);
  37.             b = Integer.parseInt(strs[1]);
  39.             while ((!queue.isEmpty()) && (queue.peek().time <= b)) {
  40.                 Message message = queue.poll();
  41.                 if (update(message.srcLink, message.dst)) {
  42.                     for (Node node : message.dst.partners) {
  43.                         queue.offer(new Message(message.dst.link, node, message.time + t));
  44.                     }
  45.                 }
  46.             }
  47.             if (strs.length == 2) {
  48.                 System.out.print(nodes[a].link.size());
  49.                 for (int block : nodes[a].link) {
  50.                     System.out.print(" " + block);
  51.                 }
  52.                 System.out.println();
  53.             } else {
  54.                 c = Integer.parseInt(strs[2]);
  55.                 nodes[a].link.add(c);
  56.                 for (Node node : nodes[a].partners) {
  57.                     queue.offer(new Message(nodes[a].link, node, b + t));
  58.                 }
  59.             }
  60. //            for (Node node:nodes){
  61. //                System.out.println(node.link);
  62. //            }
  63.         }
  64.     }
  66.     private static boolean update(List<Integer> srcLink, Node dst) {
  67.         // System.out.println(src.index+":"+src.link);
  68.         // System.out.println(dst.index+":"+dst.link);
  69.         if ((srcLink.size() > dst.link.size()) || ((srcLink.size() == dst.link.size())
  70.                 && (srcLink.get(srcLink.size() - 1) < dst.link.get(dst.link.size() - 1)))) {
  71.             dst.link = new ArrayList<>(srcLink);
  72.             return true;
  73.         }
  74.         return false;
  75.     }
  76. }
  78. /**
  79.  * 更新消息
  80.  */
  81. class Message {
  82.     List<Integer> srcLink;
  83.     Node dst;
  84.     int time;
  86.     public Message(List<Integer> srcLink, Node dst, int time) {
  87.         super();
  88.         this.srcLink = new ArrayList<>(srcLink);
  89.         this.dst = dst;
  90.         this.time = time;
  91.     }
  93. }
  95. class Node {
  96.     int index;
  97.     List<Integer> link;
  98.     List<Node> partners;
  100.     public Node(int n, int i) {
  101.         index = i;
  102.         link = new ArrayList<>(n);
  103.         link.add(0);
  104.         partners = new ArrayList<>(n);
  105.     }
  106. }