BOJ 1865번 :: 웜홀

#문제

https://www.acmicpc.net/problem/1865

#작성 코드

#include <iostream>
#include <vector>
using namespace std;
 
int tc, n, m, w;
int INF = 987654321;
int s[501];        // s[i]로 가는 최단시간 저장 
vector<pair<int,int> > p[501];
bool flag;        // 음의 사이클 발생 여부 
 
int main(){
    cin>>tc;
    while(tc--){
        // 음의 사이클 발생여부, 도로, 웜홀 연결들, s배열을 초기화해준다. 
        flag = false;
        for(int i=0; i<501; i++)
            p[i].clear();
        fill_n(s, n, INF);
        s[1] = 0;
        
        // 지점, 도로, 웜홀 개수 입력 
        cin>>n>>m>>w;
        // m개 도로 입력. 양방향. 
        for(int i=0; i<m; i++){
            int s, e, t;
            cin>>s>>e>>t;
            p[s].push_back(make_pair(e, t));
            p[e].push_back(make_pair(s, t));
        }
        // w개 웜홀 입력. 단방향. 음의 가중치.
        for(int i=0; i<w; i++){
            int s, e, t;
            cin>>s>>e>>t;
            p[s].push_back(make_pair(e, -t));
        }
        
        // 벨만 포드 알고리즘은 O(V*E)이다. 
        // 지점 개수 (V) 
        for(int i=1; i<=n; i++){
        // * 도로, 웜홀 개수(E) 
            for(int j=1; j<=n; j++){
                for(int k=0; k<p[j].size(); k++){
                    int next = p[j][k].first;
                    int cost = p[j][k].second;
                    if( s[j]!=INF && s[next]>cost+s[j]){
                        s[next] = cost + s[j];
                        if( i==n ){
                            // 음의 사이클 발생시 flag를 true로 한다. 
                            flag = true;
                        }
                    }
                }
            }
        }
        if(flag)
            cout<<"YES\n";
        else
            cout<<"NO\n";
    }
    return 0;
}

travel 함수로 벨만포드 알고리즘을 분리한 코드.

#include <iostream>
#include <vector>
using namespace std;
 
vector<pair<int,int> > p[501];
int testcase, point, road, worm;
int time[501];
int INF = 2000000000;
 
bool travel(){
    for(int i=1; i<=point; i++){
        for(int j=1; j<=point; j++){
            for(int k=0; k<p[j].size(); k++){
                int next = p[j][k].first;
                int takes = p[j][k].second+time[j];
                
                if( time[j]!=INF && takes<time[next] ){
                    if( i==point ){
                        return true;
                    }
                    time[next] = takes;
                }
            }
        }
    }
    return false;
}
 
int main(){
    cin>>testcase;
    for(int tc=0; tc<testcase; tc++){
        // 1번 지점에서 각 지점으로 가는데 걸리는 시간 무한대로 초기화 
        for(int init=0; init<501; init++){
            time[init] = INF;
        }
        // 시작 지점에서 시작지점으로 가는 시간은 0이다. 
        time[1] = 0;
        for(int i=0; i<501; i++){
            p[i].clear();
        }
        
        // 입력
        cin>>point>>road>>worm;
        for(int r=0; r<road; r++){
            int s, e, t;
            cin>>s>>e>>t;
            // 도로는 양방향(=무방향)이다. 
            p[s].push_back(make_pair(e, t));
            p[e].push_back(make_pair(s, t));
        }
        for(int w=0; w<worm; w++){
            int s, e, d;
            cin>>s>>e>>d;
            // 웜홀은 단방향이다.
            // 웜홀에서는 시간이 거꾸로 흐르므로 -d로 저장해준다. 
            p[s].push_back(make_pair(e, -d));
        }
        // 음의 사이클이 존재하면 yes
        // (음의 사이클 중 하나에서 출발하면 출발지로 돌아오면 과거가 된다.)
        if( travel() ) cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}

##

벨만포드 알고리즘 로직은 틀리지 않았는데, 자꾸 틀렸다는 판정을 받아서 원인을 찾기 힘들었다.

문제는 새로운 테스트케이스를 시작할 때 벡터p[]를 초기화해주지 않아서 이전 테스트케이스에서 입력받았던 도로, 웜홀 연결들이 남아있었기 때문이었다.

한 문제에 테스트케이스 여러 개를 입력받아서 실행한다면 매 테스트케이스마다 사용하는 변수, 배열들을 초기화해줘야 한다는 것을 잊지 말자!