[C++] 1865번 웜홀 - 벨만포드

#include <iostream>
#include <vector>

#define MAX_VERTEX 501
#define INF 987654

using namespace std;

int TC, N, M, W;  //테스트케이스의 개수, 지점의 수, 도로의 개수, 웜홀의 개수
vector<pair<pair<int, int>, int>> tr;  //간선: truck. 시작점, 도착점, 거리가 들어있음
int Dist[MAX_VERTEX];  //최소 거리
int Exist[MAX_VERTEX];  //간선이 존재하는가?
int mi;  //첫 번째 탐색 지점, 음수: minus

void Bellman_Ford(int First)
{
    Dist[First] = 0;
    for(int i=0; i<=N-1; i++) {
        for(int j=0; j<tr.size(); j++) {
            int From = tr[j].first.first;
            int To = tr[j].first.second;
            int Cost = tr[j].second;
            
            if(Dist[From] == INF) continue;  //이미 탐색이 안된 위치라면 넘기기
            if(Dist[To] > Dist[From] + Cost) {
                if(i!=N-1) Dist[To] = Dist[From] + Cost;  //비용이 더 적으면 갱신하기 
                else
                    mi=-1;
            }
        }
    }
    for(int i=1; i<=N; i++) {
        if(Dist[i]==INF && Exist[i])
            Bellman_Ford(i);  //분리되어 있는 다른 그래프도 확인
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> TC;
    for(int i=0; i<TC; i++) {
        int S, E, T;//S와 E는 연결된 지점의 번호, T는 이 도로를 통해 이동하는 데 걸리는 시간
        cin >> N >> M >> W;  //지점의 수, 도로의 개수, 웜홀의 개수
        
        tr.clear();  //tr 초기화
        for(int j=1; j<=N; j++)  //거리 초기화
            Dist[j]=INF;
        
        for(int j=0; j<M; j++) {
            cin >> S >> E >> T;
            Exist[S]=1, Exist[E]=1;
            tr.push_back({{S, E}, T});
            tr.push_back({{E, S}, T});  //간선 넣어주기. (방향 없음)
        }
        for(int j=0; j<W; j++) {
            cin >> S >> E >> T;
            Exist[E]=1;
            tr.push_back({{S, E}, -T});  //웜홀 (방향 있음)
        }
        mi=0;
        Bellman_Ford(S);
        if(mi)
            cout << "YES" << endl;
        else
            cout << "NO"  << endl;
    }
    
    return 0;
}

 

 

난 정점이 모두 연결되어야 한다고 생각하였는데 다른 사람의 코드를 보니까 꼭 그러란 법은 없는 것 같다. 정점 1과 모두 연결되어 있는듯 한데 뭐... 아 그리고 벨만 포드 알고리즘을 쓰면서 음수가 되는 회로를 구해야만하는 줄 알았는데 그 전에 자기 자신으로 음수로 돌아오기만 해도 된다고 조건을 추가하면 더 빨라지는 것 같다. 그리고 N번 돌리기 전에 최소 경로가 바뀌지 않으면 넘어간다. 라는 조건도 추가해야하는 것 같다. 참고한 다른 사람의 코드는 아래에 있다.

 

 

 

<벨만-포드 알고리즘 1>

https://velog.io/@kimdukbae/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B2%A8%EB%A7%8C-%ED%8F%AC%EB%93%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Bellman-Ford-Algorithm

[알고리즘] 벨만-포드 알고리즘 (Bellman-Ford Algorithm)

 

<벨만-포드 알고리즘 2>

https://sorjfkrh5078.tistory.com/30

벨만-포드 알고리즘(Bellman-Ford Algorithm)

 

<다른 분의 코드(맞춰야 볼 수 있습니다.)>

https://www.acmicpc.net/source/22035361

로그인

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.