글 읽기 - 시간 줄인다고 줄여봤는데 어렵네요..ㅠㅠ

cartoonman 7년 전 0

다익스트라로 구현해봤고, 다익스트라에서 최소값 뽑는걸 힙 이용하면 더 빨라진다해서 힙으로 구현해봤습니다.

일단 x에서 각 마을로 가는 시간을 구해서 weight라는 배열에 복사해두구

한명씩 x에 가는 최소 시간을 구합니다. 그다음 weight 해당 인덱스의 값과 합쳐서 최대값 비교하여 출력.. 하는데요

n명을 각각 다익스트라를 다 돌리다보니까 시간 초과가 난다고 생각이 듭니다.. 이거 어떻게 더 줄일 수 있을까요

#include <stdio.h>
#include <memory.h>

#define INT_MAX 2147483647
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 1000
#define INF 1000000000

int weight[MAX_VERTICES][MAX_VERTICES];
int distance[MAX_VERTICES];
int found[MAX_VERTICES];

typedef struct {
    int key;
    int index;
}element;
typedef struct{
    element heap[MAX_VERTICES];
    int heap_size;
}Heaptype;

void insert_max_heap(Heaptype *h, int key, int index){
    element item;
    item.key = key;
    item.index = index;
    
    int i;
    i = ++(h->heap_size);
    
    while((i!=1) && item.key>h->heap[i/2].key){
        h->heap[i] = h->heap[i/2];
        i/=2;
    }
    h->heap[i]=item;
}

element delete_max_heap(Heaptype *h){
    int parent, child;
    element item, temp;
    
    item = h->heap[1];
    temp = h->heap[(h->heap_size)--];
    parent=1;child=2;
    while(child<=h->heap_size){
        if((child<h->heap_size) && (h->heap[child].key)<h->heap[child+1].key) child++;
        if(temp.key>=h->heap[child].key) break;
        h->heap[parent] = h->heap[child];
        parent=child;
        child*=2;
    }
    h->heap[parent]=temp;
    return item;
}

void heap_sort(int n, element *item){
    Heaptype h;
    h.heap_size=0;
    
    for(int i=0;i<n;i++){
        if(!found[i]) insert_max_heap(&h, distance[i], i);
    }
    for(int i=(h.heap_size)-1;i>=0;i--){
        *item = delete_max_heap(&h);
    }
}

int choose(int n){
    int min, minpos;
    min = INT_MAX;
    minpos = -1;
    element item;
    heap_sort(n, &item);
    return item.index;
}

void shortest_path(int start, int n){
    int i, u, w;
    for(i=0;i<n;i++){
        distance[i] = weight[start][i];
        found[i]=FALSE;
    }
    found[start]=TRUE;
    distance[start]=0;
    for(i=0;i<n-2;i++){
        u=choose(n);
        found[u]=TRUE;
        for(w=0;w<n;w++)
            if(!found[w])
                if(distance[u]+weight[u][w]<distance[w] && weight[u][w]!=INF)
                    distance[w] = distance[u]+weight[u][w];
    }
}



int main(void){
    int n, m, x;
    scanf("%d %d %d", &n, &m, &x);
    
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            weight[i][j]=INF;
        }
    }
    
    for(int i=0;i<m;i++){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        if(weight[a-1][b-1]>c) weight[a-1][b-1]=c;
    }
    
    int max_weight=0;
    
    
    shortest_path(x-1, n);
    
    int weight[MAX_VERTICES];
    memcpy(weight, distance, sizeof(distance));
    for(int i=0;i<n;i++){
        if(i!=x-1){
            shortest_path(i, n);
            int temp = distance[x-1];
            temp+=weight[i];
            if(temp>max_weight) max_weight=temp;
        }
    }
    printf("%d\n", max_weight);
}

sksdong1 7년 전 2

2번의 다익스트라로 해결할 수 있습니다.

목적지를 시작점으로 돌리면 각 마을로 가는 최단거리를 한번만에 얻을 수 있죠,

하지만 단방향 도로이기 때문에 N개의 마을에서 목적지로 오는 경로는 다르게 되므로

역방향의 그래프를 하나더 만들어서 목적지에서 다익스트라 돌리면 마을에서 목적지로 오는 최단거리도 1번에 구할 수 있어요

cartoonman 7년 전 0

감사합니다. 성공했습니다.

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

문제

문제

출처

ICPC

시간 줄인다고 줄여봤는데 어렵네요..ㅠㅠ

cartoonman 7년 전 0

sksdong1 7년 전 2

cartoonman 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말