[BaekJoon][7577] 탐사

BAEKJOON ONLINE JUDGE

한국정보올림피아드 시.도 지역본선 2013

7577 탐사

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

모르겠다. 이건 다시 해석해야 할 숙제

#include <stdio.h>
 
int l, n;
int state[41][41];
 
int main()
{
    int i, j, k;
    int s, e, cnt;
 
    scanf("%d %d", &l, &n);
 
    // 플로이드 초기화
    for (i = 0; i <= l; i++) {
        for (j = 0; j <= l; j++) {
            state[i][j] = 1e9;
        }
    }
 
    state[0][0] = 0;
    for (i = 1; i <= l; i++) {
        state[i][i - 1] = state[i][i] = 0;
        // 하나씩 다 들어있다고 가정
        state[i - 1][i] = 1;
    }
 
    for (i = 0; i < n; i++) {
        scanf("%d %d %d", &s, &e, &cnt);
        // 입력이 잘 못되는 것 잡기
        // ex) 1 1 2 -> n개의 칸에 n개보다 많은 개수가 입력으로 주어질 때
        if(state[s - 1][e] > cnt)        // 미리 저장된 곳은 1칸, 0칸 짜리들
            state[s - 1][e] = cnt;
 
        // 플로이드에서 ex) 1-12는 1-8 + 9-12로 이루어 질 경우
        //                 1-8은  1-12 - 12-9를 하기 위해서 거꾸로 값은 -를 넣음
        state[e][s - 1] = cnt * -1;
    }
 
    for (k = 0; k <= l; k++) {
        for (i = 0; i <= l; i++) {
            for (j = 0; j <= l; j++)    {
                if (state[i][k] + state[k][j] < state[i][j])
                    state[i][j] = state[i][k] + state[k][j];
            }
        }
    }
 
    for (i = 0; i <= l; i++) {
        if (state[i][i] < 0) {
            printf("NONE\n");
            return 0;
        }
    }
 
    // state[0][n]은 누적값이 저장되어 있다
    for (i = 0; i < l; i++) {
        printf("%c", (state[0][i + 1] - state[0][i]) ? '#' : '-');
    }
    printf("\n");
 
    return 0;
}