글 읽기 - 벨만 포드 왜 틀렸을까요..?

beawall 2년 전 0

문제를 간단히 생각해서 그래프 전체에서 음수 가중치 사이클이 발생하면 YES, 그 외의 경우 NO를 출력하는 문제라고 생각했습니다.

그래서 모든 음수 가중치 간선에 대해 그 간선의 종점부터 시작점까지의 최단 거리를 벨만 포드로 구한 뒤에 그 거리가 음수 가중치의 절대값보다 작으면 음수 사이클이 발생한다는 뜻이고, 이것으로 모든 음수 사이클 발생 케이스를 커버한다고 생각했는데 47%쯤에서 틀립니다. 혹시 어떤 것을 잘못 생각했을지 한번만 봐주시면 감사하겠습니다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;

#define MIN(x, y) ((x) = min((x), (y)))
#define MAX(x, y) ((x) = max((x), (y)))
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define fornn(i, l) for (int i = 1; i <= int(l); i++)
#define INF (1e9)

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef struct _edge
{
    int dest, weight;
} edge;
typedef struct _info
{
    int src, dest, weight;
} info;
vector<vector<edge>> graph;
vector<info> vec;
int n, m, w;

int bellmanford(int src, int dest, int val, int *dist)
{
    dist[src] = 0;
    for (const auto &iter : graph[src])
        if (dist[iter.dest] > iter.weight)
            dist[iter.dest] = iter.weight;
    for (int i = 2; i <= n - 1; i++)
    {
        for (int t = 1; t <= n; t++)
        {
            for (const auto &iter : graph[t])
            {
                if (dist[iter.dest] > dist[t] + iter.weight)
                    dist[iter.dest] = dist[t] + iter.weight;
            }
        }
    }
    if (dist[dest] >= val)
        return 1;
    else
    {
        cout << "YES\n";
        return 0;
    }
}

void solve()
{
    cin >> n >> m >> w;
    graph.assign(n + 1, vector<edge>());
    int src, dest, weight;
    int dist[501];
    forn(i, m)
    {
        cin >> src >> dest >> weight;
        graph[src].push_back({dest, weight});
        graph[dest].push_back({src, weight});
    }
    forn(i, w)
    {
        cin >> src >> dest >> weight;
        graph[src].push_back({dest, -weight});
        vec.push_back({dest, src, weight});
    }
    for (const auto &iter : vec)
    {
        fornn(i, n)
            dist[i] = INF;
        if (bellmanford(iter.src, iter.dest, iter.weight, dist) == 0)
            return;
    }
    cout << "NO\n";
}

bool multi = true;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    if (multi)
        cin >> t;
    while (t--)
        solve();
    return 0;
}

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

문제

문제

출처

ICPC

벨만 포드 왜 틀렸을까요..?

beawall 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말