1738

Problem

• https://www.acmicpc.net/problem/1738

Logic

분석

• 문제 유형 (알고리즘…)
• 제약 조건 (인풋 크기, 예외 값, 시공간 복잡도…)

설계

1. 알고리즘 선택
2. 자료구조 선택
3. 수도 코드 작성
4. 정합판단

• 1 ~ 3과정으로 도출된 로직이 문제를 해결하는가
  • 그렇다 → 구현
  • 잘 모르겠다 → 구현
  • 아니다 → 1번부터 다시 점검

구현

• 로직 검증

테스트

• 예외 케이스 고려

My Code

cpp

boj/1738.cpp

// https://www.acmicpc.net/problem/1738
#include <iostream>
using namespace std;
 
#ifdef LOCAL
#    define LOG clog
#else
struct nullstream : ostream {
    nullstream()
        : ostream(nullptr) {}
};
nullstream LOG;
#endif
 
void fast_io() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}
 
//--------------------------------------------------------------------------------------------------
 
#define MAX (1234567891)
#define MIN (-1234567891)
 
#include <iostream>
#include <vector>
 
struct node {
    int u;
    int v;
    int w;
};
 
int main() {
    fast_io();
 
    //   logic
    int n, m, start = 0;
    cin >> n >> m;
 
    vector<node> adj(m);
    vector<int>  dist(n, MIN);
    vector<int>  predecessor(n, -1);
    dist[start] = 0;
 
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
 
        adj[i] = { u - 1, v - 1, w };
    }
 
    for (int i = 0; i < n; ++i) {
        for (const node& e: adj) {
            if (dist[e.u] != MIN && dist[e.v] < dist[e.u] + e.w) {
                // if (i == n - 1) {
                //     cout << -1;
                //     return 0;
                // }
                dist[e.v]        = dist[e.u] + e.w;
                predecessor[e.v] = e.u;
                if (i == n - 1) {
                    predecessor[e.v] = -2;
                }
            }
        }
    }
 
    if (dist[n - 1] == MAX) {
        cout << -1;
        return 0;
    }
 
    vector<int> path;
    for (int target = n - 1; target != -1; target = predecessor[target]) {
        path.push_back(target + 1);
    }
 
    reverse(path.begin(), path.end());
 
    for (const auto& i: path) {
        cout << i << " ";
    }
 
    return 0;
}
 

python

boj/1738.py

# https://www.acmicpc.net/problem/1738