글 읽기 - 다익스트라 풀이(문제 조건 수정 요청?, 꼭 답변부탁드립니다!)

minu452 1년 전 0

다익스트라 알고리즘에 모든 노드를 한번씩 찍고 돌아오는 최대 간선 수 (N-1)*2 제한(58 line)을 둬서 문제를 통과했습니다. 음의 싸이클이 생기지 않는 간선 수 내에서 최단 비용 거리를 탐색했습니다.

맞는 풀이일까요? 시작점에 다시 갔을 때 음수가 되기만 하면 되므로 음의 싸이클을 충분히 돌고 시작점으로 돌아가서 시간이 음수가 되도록 만들면 안되는 건가요? 어찌됐든 시작점으로 갔을 때 음수가 되기만 하면 되는 거 아닌가요? 문제 조건에는 최소비용을 구하라고 하지 않았는데요... suboptimal을 구하면 안되는 이유가 뭘까요..?

아래 해설 또한 '음의 싸이클을 가지면 안된다' 라는 가정을 하고 있는데 그냥 벨만 포드를 사용했기 때문에 음의 싸이클을 막는건가요?

https://www.acmicpc.net/board/view/72995

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int TC, N, M, W, S, E, T;

struct Node
{
    int vex;
    int eff;
    int cnt;
    Node(int a, int b, int c){
        vex=a;
        eff=b;
        cnt=c;
    }

    bool operator<(const Node& a) const {
        return eff > a.eff;
    }
};

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

    //freopen("input.txt", "r", stdin);
    cin >> TC;
    for (int tc=0; tc<TC; tc++){
        cin >> N >> M >> W;
        vector<vector<Node>> graph(N+1);
        for (int i=0; i<M; i++){
            cin >> S >> E >> T;
            graph[S].push_back(Node(E, T, 0));
            graph[E].push_back(Node(S, T, 0));
        }

        for (int i=0; i<W; i++){
            cin >> S >> E >> T;
            graph[S].push_back(Node(E, -T, 0));
        }

        bool flag=false;
        for (int i=1; i<=N; i++){
            priority_queue<Node> pq;
            pq.push(Node(i, 0, 0));
            vector<int> time(N+1, 2147000000);

            while (!pq.empty()){
                int vex = pq.top().vex;
                int t = pq.top().eff;
                int cnt = pq.top().cnt;
                pq.pop();
                // 음수가 됐거나 최대 간선수에 도달한경우
                if (time[i] < 0 || cnt==(N-1)*2) break;
                if (time[vex] < t) continue;
                

                for (int j=0; j<graph[vex].size(); j++){
                    int nvex = graph[vex][j].vex;
                    int nt = t+graph[vex][j].eff;
                    if (time[nvex] > nt){
                        time[nvex]=nt; 
                        pq.push(Node(nvex, nt, cnt+1));
                    }
                }
            }

            if (time[i] < 0){
                flag=true;
                break;
            }
        }
        if (flag) cout << "YES" << endl;
        else cout << "NO" << endl;
    }


    return 0;
}

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

문제

문제

출처

ICPC

다익스트라 풀이(문제 조건 수정 요청?, 꼭 답변부탁드립니다!)

minu452 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말