글 읽기 - 문제가 왜 맞는지 모르겠네요.

ldhun041203 2년 전 0

벨만-포드로 푸는데, 아래 코드에서 시작점의 값이 INF이면 continue; 로 건너뛰는 것을 제거하였더니 정답처리가 됩니다.

안되야 하는 거 아닌가요?

#include <iostream>

#include <algorithm>
#include <string>
#include <cstring>
#include <memory>
#include <cmath>

//data structure
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <utility>
#include <set>
#include <list>
#include <tuple>

#define INF 987654321
#define MAX
#define X first
#define Y second

using namespace std;

typedef pair <int, int> pii;
typedef long long ll;

//--------struct,class-area

struct Edge{int s, e, t;};

//---------variable-area

int N, M, W, Dist[501];
vector <Edge> E;

//---------function-area



//---------end

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);

//----------start

    int TC; cin >> TC;
    while (TC--) {
        cin >> N >> M >> W;

        E.clear();
        int a, b, c;
        for (int i = 1; i <= M; i++) {
            cin >> a >> b >> c;
            E.push_back({a,b,c});
            E.push_back({b,a,c});
        }
        for (int i = 1; i <= W; i++) {
            cin >> a >> b >> c;
            E.push_back({a,b,-c});
        }

        for (int i = 1; i <= N; i++) Dist[i] = INF;
        Dist[1] = 0;

        int flag = 0;
        for (int i = 1; i <= N; i++) {
            for (auto j : E) {
                if(Dist[j.s] == INF) continue;

                if(Dist[j.s] + j.t < Dist[j.e]) {
                    if (i == N) flag = 1;
                    Dist[j.e] = Dist[j.s] + j.t;
                }
            }
        }

        if (flag) cout << "YES\n";
        else cout << "NO\n";

    }

//-----------end

    return 0;
}

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

문제

문제

출처

ICPC

문제가 왜 맞는지 모르겠네요.

ldhun041203 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말