글 읽기 - 다익스트라 반례 부탁드립니다..

shinbian11 3년 전 0

반례가 떠오르지 않네요. 어디가 잘못된 부분일까요? 반례나 힌트만 부탁드립니다.

#include <bits/stdc++.h>

// F_I 사용하면 cin 과 scanf 를 섞어서 쓰면 안된다!
#define F_I ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;

ll Min(ll a, ll b) { return (a < b) ? a : b; }
ll Max(ll a, ll b) { return (a < b) ? b : a; }
ll gcd(ll m, ll n) { if (n == 0) return m; return gcd(n, m % n); } //최대공약수
ll lcm(ll m, ll n) { return m * n / gcd(m, n); } //최소공배수

vector<pi> v[1004];
vector<int> ans;
int d[1004];
int from[1004];
bool visited[1004];
int INF = 987654321;
int cnt;

void printPath(int x)
{

    if (from[x] != -1)
        printPath(from[x]);

    cnt += 1;
    ans.push_back(x);
}

int main()
{
    F_I;

    //[백준] 11779번 : 최소비용 구하기 2 (우선순위 큐를 이용한 다익스트라 + 경로 출력까지!)

    int n;
    cin >> n;
    
    int m;
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        int s, e, cost;
        cin >> s >> e >> cost;
        v[s].push_back({ e,cost });
    }
    
    for (int i = 1; i <= n; i++)
        d[i] = INF;

    int start, end;
    cin >> start >> end;

    d[start] = 0;
    from[start] = -1;

    priority_queue< pi, vector<pi>, greater<pi> > q; //{node, cost}
    q.push({ start,0 });

    while (!q.empty())
    {
        auto t = q.top();
        q.pop();
        int x = t.first;

        if (visited[x])
            continue;

        visited[x] = true;

        for (auto t : v[x])
        {
            int y = t.first;
            int cost = t.second;

            if (d[y] > d[x] + cost)
            {
                d[y] = d[x] + cost;
                from[y] = x;

                q.push({ y,d[y] });
            }
        }
    }

    cout << d[end] << '\n';

    printPath(end);

    cout << cnt << '\n';
    
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << ' ';

    return 0;
}

adxx 3년 전 1

q.push({ start,0 });

거리, 정점 순으로 queue에 push 해야합니다

현재는 정점 순으로 pq가 정렬되고 있는걸로 보입니다

shinbian11 3년 전 0

감사합니다!

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

문제

문제

출처

ICPC

다익스트라 반례 부탁드립니다..

shinbian11 3년 전 0

adxx 3년 전 1

shinbian11 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말