글 읽기 - 최단경로 질문입니다...

lg970325 7년 전 0

큐를 써서 풀어봤는데요...

다 잘 나오는 것 같은데 틀렸다고 떠요..

반례가 있나요?

아니면 자료형이 문제인가요?

#include<stdio.h>
#include<stdlib.h>

typedef struct _NODE
{
    int num;
    struct _NODE* next;
} node;

typedef struct _EDGE
{
    int start,end;
    int cost;
} edge;

node* front=NULL;
node* rear=NULL;

void enqueue(node* temp)
{
    if(front==NULL)
    {
        front=temp;
        rear=temp;
    }
    else
    {
        rear->next=temp;
        rear=temp;
    }
}

node* dequeue(void)
{
    node* temp=front;
    
    front=front->next;
    if(front==NULL)
        rear=NULL;
    
    return temp;
}

int main(void)
{
    int n,k,i,s;
    int visit[25000]={0};

    node* tmp;
    scanf("%d %d",&n,&k);
    scanf("%d",&s);
    
    edge* ed=(edge*)malloc(sizeof(edge)*k);
    
    int *sum=(int*)calloc(sizeof(int),(n+1));
    
    for(i=0;i<k;i++)
        scanf("%d %d %d",&ed[i].start,&ed[i].end,&ed[i].cost);
    
    node* temp=(node*)malloc(sizeof(node));
    temp->num=s;
    temp->next=NULL;
    visit[s]++;
    enqueue(temp);
    
    while(front!=NULL)
    {
        
        tmp=dequeue();
        
        for(i=0;i<n;i++)
            if(ed[i].start==tmp->num)
            {
                if(visit[ed[i].end]==0)
                {
                    node* temp=(node*)malloc(sizeof(node));
                    temp->num=ed[i].end;
                    temp->next=NULL;
                    enqueue(temp);
                    sum[ed[i].end]=sum[ed[i].start]+ed[i].cost;
                    visit[ed[i].end]++;
                }
            }
        free(tmp);
    }
    
    for(i=1;i<=n;i++)
    {
        if(i==s)
            printf("0\n");
        
        else if(visit[i]==0)
            printf("INF\n");
        
        else
            printf("%d\n",sum[i]);
    }
    
    return 0;
}

yukariko 7년 전 0

다익스트라 같은 최단경로 알고리즘이 필요한데

이 경우는 그냥 bfs로 보이네요.

코드에도 문제점이 있긴 하지만 우선 다른 알고리즘이 필요합니다.

lg970325 7년 전 0

감사합니다!

코드의 문제점을 고치고 bfs로 해도 시간초과가 뜬다는 말씀인가요??

yukariko 7년 전 0

bfs는 간선의 가중치가 없는 경우(혹은 하나로 고정된 경우)에만 최단경로를 찾을 수 있는 알고리즘입니다.

따라서 이 문제에는 적용되지 않습니다.

lg970325 7년 전 0

다익스트라 알아봐야겠네요...

감사합니다!

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

문제

문제

출처

ICPC

최단경로 질문입니다...

lg970325 7년 전 0

yukariko 7년 전 0

lg970325 7년 전 0

yukariko 7년 전 0

lg970325 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말