글 읽기 - 이 코드가 왜 맞는지를 모르겠습니다.

mellllon 5년 전 2

이 코드에 따르면

47번 줄에 우선순위큐에 다음 릴렉스 할 위치와 cost를 넣을 때

pq.push(make_pair(nthere,ncost)); 로 구현되어있습니다.

그런데 제가 알기로는 우선순위 큐에 pair(a,b)를 넣으면

a를 우선적으로 비교하여 정렬하고, a가 같으면 b를 비교하여 정렬하는 것으로 알고있는데

저 코드대로라면 한 지점에서 릴렉스를 수행 한 뒤 다음 릴렉스할 장소를 최소 cost의 장소에서 하는 것이 아닌

단순히 꼭지점의 index 번호를 기준으로 수행하여 릴렉스 횟수를 늘리고 불필요한 연산을 하게 되는것 아닌가요??

이런 경우에 불필요하게 여러번 빙글빙글 도는거 같은데

4 6 1

1 3 20

1 2 9

3 2 2

2 3 1

2 4 6

3 4 3

왜 이 코드가 정답으로 나오는지 모르겠습니다

#include<cstdio>
#include <vector>
#include <queue>
using namespace std;
#define INF 8765432
#define MAX 20001
 
vector<pair<int,int>> ori[MAX];
 
 
int main()
{
    int V,E;
    scanf("%d %d",&V,&E);
    int K;
    scanf("%d",&K);
 
    for(int i=0; i<E; i++)
    {
        int s,e,w;
        scanf("%d %d %d",&s,&e,&w);
        ori[s].push_back(make_pair(e,w));
    }
 
    vector<int> dist(V+1,INF);
    dist[K] = 0;
 
    priority_queue<pair<int,int>> pq;
    pq.push(make_pair(K,0));
 
    while(!pq.empty())
    {    
        int here = pq.top().first;
        int cost = pq.top().second;
        pq.pop();
        
        if(cost > dist[here])continue;
        for(int i=0; i<ori[here].size(); i++)
        {
            int nthere = ori[here][i].first;
            int ncost = cost + ori[here][i].second;
            if(ncost < dist[nthere])
            {
                dist[nthere] = ncost;
                pq.push(make_pair(nthere,ncost));
            }
        }
    }
 
    for(int i=1; i<=V; i++)
    {
        if(dist[i] == INF)
            printf("INF\n");
        else
            printf("%d\n",dist[i]);
    }
 
}

startlink 5년 전 0

Dijkstra 알고리즘

epikem 5년 전 0

정말이네요. 게다가 first second 순서를 바꿔서 cost를 기준으로 하면 오히려 시간초과가 나네요.

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

문제

문제

출처

ICPC

이 코드가 왜 맞는지를 모르겠습니다.

mellllon 5년 전 2

startlink 5년 전 0

epikem 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말