7577번: 탐사

https://www.acmicpc.net/problem/7577

#include<stdio.h>
int l, n, w[41][41];
int main() {
    scanf("%d %d", &l, &n);
    for (int i = 0; i <= l; i++)
        for (int j = 0; j <= l; j++) if (i != j) w[i][j] = 1e9;
    for (int i = 0; i < l; i++) w[i + 1][i] = 0, w[i][i + 1] = 1;
    for (int i = 0, x, y, z; i < n; i++) {
        scanf("%d %d %d", &x, &y, &z);
        if (w[x - 1][y]>z) w[x - 1][y] = z;
        w[y][x - 1] = -z;
    }
    for (int i = 0; i <= l; i++)
        for (int j = 0; j <= l; j++)
            for (int k = 0; k <= l; k++)
                if (w[j][i] + w[i][k]<w[j][k]) w[j][k] = w[j][i] + w[i][k];
    for (int i = 0; i <= l; i++) if (w[i][i] < 0) {
        puts("NONE");
        return 0;
    }
    for (int i = 0; i < l; i++) putchar(w[0][i + 1] - w[0][i] ? '#' : '-');
    return 0;
}