글 읽기 - c++ 다익스트라 틀렸습니다.

ssh9199 1년 전 0

20%에서 틀립니다.

같은 시점, 종점을 가지는 여러 개의 간선이 있는 경우

N=1인 경우

를 고려하기 전, 후 모두 20%에서 틀렸습니다.

도와주세요..

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define INF 2000000002;
#define pq priority_queue<Bus, vector<Bus>, CompareBus>

int N, M, S, E;
struct Bus
{
    int to, cost;
    Bus(int t, int c)
    {
        to = t;
        cost = c;
    }
};
struct CompareBus
{
    bool operator() (Bus& b1, Bus& b2)
    {
        return b1.cost > b2.cost;
    }
};
struct City
{
    int minumumCost = INF; // from start
    pq buses;
};

City* cities;
pq q;

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

    cin >> N;
    if(N == 1)
    {
        cout << 0;
        return 0;
    }
    cin >> M;
    cities = new City[N];

    for (int i = 0; i < M; ++i)
    {
        int a, b, c; cin >> a >> b >> c; a--; b--;
        cities[a].buses.push(Bus(b, c));
    }

    cin >> S >> E; S--; E--;
    q.push(Bus(S, 0));
    cities[S].minumumCost = 0;

    while(!q.empty())
    {
        Bus bus = q.top(); q.pop();
        City* city = cities + bus.to;

        while(!city->buses.empty())
        {
            Bus nextBus = city->buses.top(); city->buses.pop();
            City* nextCity = cities + nextBus.to;
            int w = city->minumumCost + nextBus.cost;

            if(w >= nextCity->minumumCost) continue;

            nextCity->minumumCost = w;
            q.push(nextBus);
        }
    }

    cout << cities[E].minumumCost;

    return 0;
}

kokosoko59 1년 전 1

다익스트라 알고리즘에서 priority_queue에 넣고 관리하는건 간선이 아니라 노드입니다.

현재까지 방문한 노드에 연결되어있는 간선 중에서 가장 가중치가 낮은 간선으로 가는 것이 아니라, 현재까지 방문한 노드에 연결되어있는 노드 중에서 시작점으로부터 거리가 가장 짧은 노드를 방문해야합니다.

ssh9199 1년 전 1

@kokosoko59 정말 감사합니다!

cities를 CompareBus보다 먼저 선언하고,

City의 buses를 pq가 아닌 queue<int>로 바꿔준 다음,

CompareBus의 return값을 cities[b1.to].minimumCost > cities[b2.to].minimumCost로만 바꿔주었더니 AC 나왔습니다.

즉 여전히 간선을 pq에 넣었으나 그 기준을 그 간선의 끝점(to)으로 했더니 됐습니다.

kokosoko59 1년 전 1

그렇게 해도 되겠네요! 풀이 공유해주셔서 감사합니다.

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

문제

문제

출처

ICPC

c++ 다익스트라 틀렸습니다.

ssh9199 1년 전 0

kokosoko59 1년 전 1

ssh9199 1년 전 1

kokosoko59 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말