201912-4 区块链

输入输出样例

样例1

输入

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
1 27
1 1 1
2 1 2
3 1 3
4 1 4
5 1 5
1 1
2 1
3 1
4 1
5 1
1 2
2 2
3 2
4 2
5 2
1 10 10
2 11 9
1 11
2 11
3 11
4 11
5 11
1 12
2 12
3 12
4 12
5 12

输出

2 0 1
2 0 2
2 0 3
2 0 4
2 0 5
2 0 1
2 0 1
2 0 1
2 0 1
2 0 1
3 0 1 10
4 0 1 10 9
3 0 1 10
3 0 1 10
3 0 1 10
4 0 1 10 9
4 0 1 10 9
4 0 1 10 9
4 0 1 10 9
4 0 1 10 9

样例2

输入

15 13
1 2
2 3
3 4
4 5
1 6
6 7
7 8
8 9
1 10
10 11
11 12
12 13
14 15
6 28
1 1 1
1 2 2
1 6
2 7
13 7
9 7
5 7
3 14
8 14
5 14
11 14
9 25
5 25
13 25
9 29 3
5 29 4
13 29 5
1 53
2 59 6
2 59
1 1000
3 1000
8 1000
9 1000
10 1000
13 1000
14 1000
15 1000

输出

3 0 1 2
2 0 1
1 0
1 0
1 0
3 0 1 2
1 0
1 0
3 0 1 2
2 0 1
2 0 1
2 0 1
4 0 1 2 3
5 0 1 2 3 6
5 0 1 2 3 6
5 0 1 2 3 6
5 0 1 2 3 6
5 0 1 2 3 6
5 0 1 2 3 6
5 0 1 2 3 6
1 0
1 0

题解一

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = reader.readLine().split(" ");
        int n = Integer.parseInt(strs[0]);
        int m = Integer.parseInt(strs[1]);
        Node[] nodes = new Node[n + 1];
        for (int i = 0; i <= n; ++i) {
            nodes[i] = new Node(n, i);
        }
        for (int i = 0, u, v; i < m; ++i) {
            strs = reader.readLine().split(" ");
            u = Integer.parseInt(strs[0]);
            v = Integer.parseInt(strs[1]);
            nodes[u].partners.add(nodes[v]);
            nodes[v].partners.add(nodes[u]);
        }
        strs = reader.readLine().split(" ");
        int t = Integer.parseInt(strs[0]);
        int k = Integer.parseInt(strs[1]);
        // 更新消息队列
        Queue<Message> queue = new LinkedList<>();
        for (int i = 0, a, b, c; i < k; ++i) {
            strs = reader.readLine().split(" ");
            a = Integer.parseInt(strs[0]);
            b = Integer.parseInt(strs[1]);
            while ((!queue.isEmpty()) && (queue.peek().time <= b)) {
                Message message = queue.poll();
                if (update(message.srcLink, message.dst)) {
                    for (Node node : message.dst.partners) {
                        queue.offer(new Message(message.dst.link, node, message.time + t));
                    }
                }
            }
            if (strs.length == 2) {
                System.out.print(nodes[a].link.size());
                for (int block : nodes[a].link) {
                    System.out.print(" " + block);
                }
                System.out.println();
            } else {
                c = Integer.parseInt(strs[2]);
                nodes[a].link.add(c);
                for (Node node : nodes[a].partners) {
                    queue.offer(new Message(nodes[a].link, node, b + t));
                }
            }
//            for (Node node:nodes){
//                System.out.println(node.link);
//            }
        }
    }
    private static boolean update(List<Integer> srcLink, Node dst) {
        // System.out.println(src.index+":"+src.link);
        // System.out.println(dst.index+":"+dst.link);
        if ((srcLink.size() > dst.link.size()) || ((srcLink.size() == dst.link.size())
                && (srcLink.get(srcLink.size() - 1) < dst.link.get(dst.link.size() - 1)))) {
            dst.link = new ArrayList<>(srcLink);
            return true;
        }
        return false;
    }
}
/**
 * 更新消息
 */
class Message {
    List<Integer> srcLink;
    Node dst;
    int time;
    public Message(List<Integer> srcLink, Node dst, int time) {
        super();
        this.srcLink = new ArrayList<>(srcLink);
        this.dst = dst;
        this.time = time;
    }
}
class Node {
    int index;
    List<Integer> link;
    List<Node> partners;
    public Node(int n, int i) {
        index = i;
        link = new ArrayList<>(n);
        link.add(0);
        partners = new ArrayList<>(n);
    }
}