[PAT-A] 1032 Sharing

Java

测试点5超时

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.Map;

public class Main {
    private static final int N = 100010;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String[] input = reader.readLine().split(" ");
        int h1 = Integer.parseInt(input[0]);
        int h2 = Integer.parseInt(input[1]);
        int n = Integer.parseInt(input[2]);

        Map<Integer, Node> nodes = new HashMap<>();

        for (int i = 0; i < n; ++i) {
            input = reader.readLine().split(" ");
            int addr = Integer.parseInt(input[0]);
            char data = input[1].charAt(0);
            int next = Integer.parseInt(input[2]);
            nodes.put(addr, new Node(addr, data, next));
        }

        boolean[] hash = new boolean[N];

        for (int p = h1; p != -1; p = nodes.get(p).next) {
            hash[p] = true;
        }

        int p;
        for (p = h2; p != -1; p = nodes.get(p).next) {
            if (hash[p]) {
                System.out.printf("%05d\n", p);
                break;
            }
        }

        if (p == -1) {
            System.out.println("-1");
        }
    }

    static class Node {
        int addr;
        char data;
        int next;

        Node(int addr, char data, int next) {
            this.addr = addr;
            this.data = data;
            this.next = next;
        }
    }
}

C++

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, h1, h2;
int e[N], ne[N];
bool st[N];

int main() {
    cin >> h1 >> h2 >> n;

    for (int i = 0; i < n; ++i) {
        int addr, next;
        char data;
        cin >> addr >> data >> next;
        e[addr] = data;
        ne[addr] = next;
    }

    for (int p = h1; p != -1; p = ne[p]) st[p] = true;

    int p;
    for (p = h2; p != -1; p = ne[p])
        if (Hash[p]) {
            printf("%05d\n", p);
            break;
        }

    if (p == -1) cout << "-1" << endl;

    return 0;
}