글 읽기 - 타임머신 질문입니다.

haung921209 3년 전 0

우선, bellmanFord의 return 자료형의 경우, int로 하였을 때는 출력초과, 그리고 long long으로 했을 때는 틀렸습니다가 나왔습니다.

1. 우선, 출력 초과가 나올 요건이 되나요....? int일 때, 최대 -10000이므로, 사이클을 진짜 빽빽하게 돌아도 한번 돌았을 때 int의 하방에 닿았다고 이야기 못 할 수준인 것 같아서요.....

2. long long으로 했을 때, 틀린 이유를 잘 모르겠습니다. 사실 해당하는 코드는 종만북에서 참조한 코드이거든요. 저는 그냥 단순 BellmanFord로 생각하고, 해당 책과 거의 동일하게 작성하여 제출하였는데, 고려 못한 조건이 있을까요...?

아무리 생각해도 왜 오답으로 체크가 되는지 의심 가는 부분이 없어서요.

혹시, 반례라도 부탁 드려도 될까요? 감사합니다.

#pragma warning(disable:4996)
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <set>
#define MAX 26
#define INF 987654321
#define MAX_V 501
#define ull unsigned long long
#define ll long long
#define pa pair<int, int>
using namespace std;

int n, m;
vector<vector<pair<int, int>>> adj;

vector<ll> bellmanFord(int src) {
    vector<ll> upper(n, INF);

    upper[src] = 0;

    bool updated = false;

    for (int iter = 0; iter < n; iter++) {
        updated = false;
        for (int here = 0; here < n; here++)
            for (int i = 0; i < adj[here].size(); i++) {
                int there = adj[here][i].first;
                int cost = adj[here][i].second;

                if (upper[there] > upper[here] + cost) {
                    upper[there] = upper[here] + cost;
                    updated = true;
                }
            }
        if (!updated) break;
    }
    if (updated)upper.clear();
    return upper;

}




int main(void) {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n >> m;
    adj = vector<vector<pa>>(n, vector<pa>());
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a-1].push_back({ b-1,c });
    }
    vector<ll> res = bellmanFord(0);
    if (res.empty())
        cout << -1 << endl;
    else {
        for (int i = 1; i < res.size(); i++) {
            if (res[i] != INF)
                cout << res[i] << endl;
            else
                cout << -1 << endl;
        }
    }

    
    return 0;
}

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

문제

문제

출처

ICPC

타임머신 질문입니다.

haung921209 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말