글 읽기 - 다익스트라 입문하는중 ㅠㅠ 18프로에서 틀리는데 도와주세요ㅠㅠ

jakehsj 7년 전 0

최소 heap을 이용하여 나름 열심히 짜봤는데 어디가 틀린걸까요?ㅠㅠ

#include <stdio.h>
#include <queue>
#include <vector>
#include <functional>
#define INF 8765432
#define max_v 20202
using namespace std;

typedef pair<int,int> node;

vector<pair<int,int> > adj[max_v];

priority_queue<node,vector<node>,greater<node> > q;

int main()
{
    int v,e;
    scanf("%d %d",&v,&e);
    int k;
    scanf("%d",&k);
    for(int i=0;i<e;i++)
    {
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        adj[u].push_back(make_pair(v,w));
    }
    vector<int> dist(v+1,INF);
    dist[k]=0;
    q.push(node(0,k));
    while(!q.empty())
    {
        int cost=q.top().first;
        int here=q.top().second;
        q.pop();
        if(cost>dist[here]) continue;
        for(int i=0;i<adj[here].size();i++)
        {
            int where=adj[here][i].first;
            int ncost=adj[here][i].second+cost;
            if(dist[where]>ncost)
            {
                dist[where]=ncost;
                q.push(node(ncost,where));
            }
        }
    }
    for(int i=1;i<=v;i++)
    {
        if(dist[i]==INF)
            printf("INF");
        else
            printf("%d\n",dist[i]);
    }
    return 0;
}

gallopsys 7년 전 2

printf("INF");에서 newline('\n')을 출력하지 않아서 그런 거 아닐까요?

예제 테스트 케이스에서 출발 노드를 다음과 같이 1에서 2로 바꾸어보면 알 수 있을 겁니다.

5 6
2
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

jakehsj 7년 전 0

아하 거기서 틀렸었네요 덕분에 100프로 성공 했습니다 갑사합니다!!!

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

문제

문제

출처

ICPC

다익스트라 입문하는중 ㅠㅠ 18프로에서 틀리는데 도와주세요ㅠㅠ

jakehsj 7년 전 0

gallopsys 7년 전 2

jakehsj 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말