Java
测试点3、4超时
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
public class Main {
static final int N = 100010;
static int h, n;
static int[] e = new int[N];
static int[] ne = new int[N];
static boolean[] st = new boolean[N];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
h = Integer.parseInt(input[0]);
n = Integer.parseInt(input[1]);
for (int i = 0; i < n; i++) {
String[] line = br.readLine().split(" ");
int addr = Integer.parseInt(line[0]);
int key = Integer.parseInt(line[1]);
int next = Integer.parseInt(line[2]);
e[addr] = key;
ne[addr] = next;
}
List<Integer> a = new ArrayList<>();
List<Integer> b = new ArrayList<>();
for (int i = h; i != -1; i = ne[i]) {
int v = Math.abs(e[i]);
if (st[v]) {
b.add(i);
} else {
st[v] = true;
a.add(i);
}
}
for (int i = 0; i < a.size(); i++) {
System.out.printf("%05d %d ", a.get(i), e[a.get(i)]);
if (i + 1 == a.size()) {
System.out.println("-1");
} else {
System.out.printf("%05d\n", a.get(i + 1));
}
}
for (int i = 0; i < b.size(); i++) {
System.out.printf("%05d %d ", b.get(i), e[b.get(i)]);
if (i + 1 == b.size()) {
System.out.println("-1");
} else {
System.out.printf("%05d\n", b.get(i + 1));
}
}
}
}
C++
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 100010;
int n;
int h, e[N], ne[N];
bool st[N];
int main() {
scanf("%d%d", &h, &n);
for (int i = 0; i < n; i++) {
int addr, key, next;
scanf("%d%d%d", &addr, &key, &next);
e[addr] = key, ne[addr] = next;
}
vector<int> a, b;
for (int i = h; i != -1; i = ne[i]) {
int v = abs(e[i]);
if (st[v]) b.push_back(i);
else {
st[v] = true;
a.push_back(i);
}
}
for (int i = 0; i < a.size(); i++) {
printf("%05d %d ", a[i], e[a[i]]);
if (i + 1 == a.size()) puts("-1");
else printf("%05d\n", a[i + 1]);
}
for (int i = 0; i < b.size(); i++) {
printf("%05d %d ", b[i], e[b[i]]);
if (i + 1 == b.size()) puts("-1");
else printf("%05d\n", b[i + 1]);
}
return 0;
}