글 읽기 - 이거 그냥 다익스트라 문제 아닌가요?

minsung05 3년 전 1

제가 뭘 잘못했는지 잘 모르겠습니다....

다익스트라에서 갈 수 있는 경로의 수를 찾고, 그 최댓값을 찾았는데

혹시 이게 아닌가요?

#include<stdio.h>
#include<vector>
#include<queue>
#define INF 100000000
#define amend(a) a>=INF? -1 : a
#define I(a) a >= INF? 0 : 1
#define max(a,b) a>b?a:b
using std::vector; using std::pair; using std::priority_queue; using std::greater;
int main()
{
    int Q;
    scanf("%d",&Q);
    while(Q--)
    {
        vector<pair<int,int> > g[10005];
        int n,d,c;
        scanf("%d %d %d",&n,&d,&c);
        while(d--)
        {
            int p,q,r;
            scanf("%d %d %d",&p,&q,&r);
            g[q].push_back({p,r});
        }
        int dist[10005];
        bool chk[10005] = {0,};
        for(int i = 1; i <= n ; i++) dist[i] = INF;
        priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
        dist[c] = 0; pq.push({0,c}); //chk[c] = true;
        while(!pq.empty())
        {
            int a = pq.top().second; pq.pop();
            if(chk[a]) continue;
            chk[a] = true;
            vector<pair<int,int> >::iterator it = g[a].begin();
            while(it != g[a].end())
            {
                if(dist[a] + it->second < dist[it->first] and !chk[it->first])
                    pq.push({dist[it->first] = dist[a] + it->second, it->first});
                it++;
            }
        }
        //for(int i = 1; i<=n; i++) printf("%d ",dist[i]);
        //printf("\n");
        int ans = 0, M = 0;
        for(int i = 1; i<=n; i++) ans += I(dist[i]);
        for(int i = 1; i<=n; i++) M = max(amend(dist[i]),M);
        printf("%d %d\n",ans,M);
    }
}

djm03178 3년 전 0

매크로 함수는 꼭 필요한 경우가 아니면 사용을 자제하는 것이 좋습니다. 꼭 사용해야겠다면 그 동작 원리를 정확히 알고, 모든 인자에 괄호를 철저하게 치는 것이 좋습니다. 46번째 줄의 매크로 함수들이 변환된 결과가 의도한 연산자 우선순위와 다르게 묶입니다. 이 부분만 괄호를 잘 쳐주면 맞습니다.

minsung05 3년 전 0

ㅠㅠㅠ 감사합니다

이런 실수가 있을 줄이야ㅠㅠ

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

문제

문제

출처

ICPC

이거 그냥 다익스트라 문제 아닌가요?

minsung05 3년 전 1

djm03178 3년 전 0

minsung05 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말