# TopCoder

\begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align}

33.3% (1/3)

40.0% (2/5)

# Description

Petya 在看完犯罪現場調查這題之後，決定自己也來練習看看。但是因為 Petya 在寫的時候沒有很認真思考，導致他寫出了錯誤的程式，在上傳之後得到了一個 WA。以下是他寫的程式：

#include <cstdio>

const int kMaxN = 1001, kInf = 100000001;
int x[kMaxN][kMaxN];

int main() {
int N, M;
scanf("%d%d", &N, &M);
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= N; j++) x[i][j] = kInf;
}
for (int i = 0; i <= N; i++) x[i][i] = x[0][i] = 0;
while (M--) {
int a, b, d;
scanf("%d%d%d", &a, &b, &d);
if (-d < x[b][a]) x[b][a] = -d;
}
for (int k = 0; k <= N; k++) {
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= N; j++) {
if (x[i][j] - x[i][k] > x[k][j]) x[i][j] = x[i][k] + x[k][j];
}
}
}
for (int i = 0; i <= N; i++) {
if (x[i][i] < 0) {
puts("-1");
return 0;
}
}
for (int i = 1; i <= N; i++) printf("%d\n", x[0][i]);
}


# Problem Source

Problem Set by Yihda Yol

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 20
8 7 20

# Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 500 32768 65536 1
1 500 32768 65536 2
2 500 32768 65536 3
3 500 32768 65536 4
4 500 32768 65536 5
5 500 32768 65536 6
6 500 32768 65536 7
7 500 32768 65536 8