글 읽기 - 2개 코드의 차이를 모르겠어요ㅠㅠ

dnflekals 2년 전 0

첫 번째 코드는 틀린 코드이고, 두 번째 코드는 맞은 코드입니다.

두 개 차이라곤 41 라인과 103 라인뿐인데, 왜 두 번째 코드만 맞는건가요??ㅠㅠ

고수님들 도와주시면 감사하겠습니다...

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <string>
#include <iostream>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>
#include <functional>
#include <map>
using namespace std;
vector <pair<int, int>> g[105];
long long dist[105];
int p[105];

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    for (int i = 0;i < m;i++) {
        int a, b, c; cin >> a >> b >> c;
        g[a].push_back({ b,c });
    }
    for (int i = 0;i <= n;i++) dist[i] = -1e18;
    dist[1] = 0;
    
    bool cycle = false;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            if (dist[j] == -1e18) continue;
            for (int k = 0;k < g[j].size();k++) {
                int nx = g[j][k].first;
                int ncost = g[j][k].second;

                if (dist[nx] < dist[j] + ncost) {
                    dist[nx] = dist[j] + ncost;
                    p[nx] = j;

                    if (i == n) cycle = true;
                }
            }
        }
    }

    if (cycle == true) cout << "-1\n";
    else {
        vector <int> ans;
        int now = n;
        while (now != 0) {
            ans.push_back(now);
            now = p[now];
        }
        for (int i = ans.size() - 1;i >= 0;i--) {
            cout << ans[i] << " ";
        }
    }

    return 0;
}


#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <string>
#include <iostream>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>
#include <functional>
#include <map>
using namespace std;
vector <pair<int, int>> g[105];
long long dist[105];
int p[105];

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    for (int i = 0;i < m;i++) {
        int a, b, c; cin >> a >> b >> c;
        g[a].push_back({ b,c });
    }
    for (int i = 0;i <= n;i++) dist[i] = -1e18;
    dist[1] = 0;

    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            if (dist[j] == -1e18) continue;
            for (int k = 0;k < g[j].size();k++) {
                int nx = g[j][k].first;
                int ncost = g[j][k].second;

                if (dist[nx] < dist[j] + ncost) {
                    dist[nx] = dist[j] + ncost;
                    p[nx] = j;

                    if (i == n) dist[nx] = 1e18;
                }
            }
        }
    }

    if (dist[n] == 1e18) cout << "-1\n";
    else {
        vector <int> ans;
        int now = n;
        while (now != 0) {
            ans.push_back(now);
            now = p[now];
        }
        for (int i = ans.size() - 1;i >= 0;i--) {
            cout << ans[i] << " ";
        }
    }

    return 0;
}

jms020820 1년 전 0

첫번째는 사이클의 존재여부만 확인했지 사이클에서 n으로 갈 수 있는지는 확인하지 않고

두번째는 i==n 일때 dist[nx] 가 1e18로 갱신되었다는 것은 nx 가 사이클에 포함되거나 사이클에서 nx로 도달 가능한 것을 의미하니 정답인거 같습니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2개 코드의 차이를 모르겠어요ㅠㅠ

dnflekals 2년 전 0

jms020820 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말