글 읽기 - 1865 웜홀 , 반례

sch0115 4년 전 0

게시판에 있는 반례랑 테스트 케이스는 다 맞게 나오는데 어디 부분이 잘못된걸까요ㅠㅠ 고수분들 도와주세요

// ConsoleApplication1.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

#include <iostream>
#include <queue>
#include <vector>
#include <string.h>
#include <algorithm>
#include <map>
#include <math.h>
using namespace std;

#define MAX_N 503
#define INF 987654321

struct edge {
    int nodeNum, value;
};
int t;
int n, m, w;
vector<edge> graph[MAX_N];
int _dist[MAX_N];
int _cycle[MAX_N];
bool _inQ[MAX_N];


void init(){
    for (int i = 0; i <= n; ++i) {
        _dist[i] = INF;
        _cycle[i] = 0;
        _inQ[i] = false;
    }
}

bool SPFA(int startNode, int dist[], int cycle[], bool inQ[]){

    queue<int> que;
    dist[startNode] = 0;
    inQ[startNode] = true;
    que.push(startNode);

    while(!que.empty()){
        int cur = que.front();
        que.pop();
        inQ[cur] = false;

        for (int i = 0; i < graph[cur].size(); ++i) {
            int nextNode = graph[cur][i].nodeNum;
            int nextValue = graph[cur][i].value;
            bool isUpdate = dist[cur] + nextValue < dist[nextNode];
            if(!isUpdate) continue;
            dist[nextNode] = dist[cur] + nextValue;
            if(inQ[nextNode]) continue;
            if(cycle[nextNode] >= n-1){
                return false;
            }
            que.push(nextNode);
            inQ[nextNode] = true;
            cycle[nextNode]++;
        }
    }

    return true;
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> t;

    while(t--){
        int s,e,v;
        bool isNCycle;
        string ans;
        cin >> n >> m >> w;


        for (int i = 0; i < m; ++i) {
            cin >> s >> e >> v;
            graph[s].push_back({e,v});
            graph[e].push_back({s,v});
        }

        for (int i = 0; i < w; ++i) {
            cin >> s >> e >> v;
            graph[s].push_back({e,v*-1});
        }

        for (int i = 1; i <= n; ++i) {
            init();
            isNCycle = !SPFA(i, _dist, _cycle, _inQ);
            if(isNCycle) break;
        }

        ans = isNCycle ? "YES" : "NO";
        cout << ans << "\n";

        for (int i = 1; i <= n; ++i) {
            graph[n].clear();
        }
    }


}

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

문제

문제

출처

ICPC

1865 웜홀 , 반례

sch0115 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말