글 읽기 - 시간초과 해결해주세요 ㅠ ㅠ

yoonfy4280 5년 전 0

Heap을 직접 구현해서 푼걸로는 해결 됐는데,,,, STL써서 푼 문제는 시간초과가 계속 뜨네요 ㅠ ㅠ....

adj로 인접리스트를 생성해주고 우선순위 큐에 다가 adj에 있던 내용물을 넣어 줬는데,,,,

여기서 우선순위 큐가 가장 작은 값을 못 빼주는 것 같아서 시간 초과가 나오는 것 같은데,,,,, 왜 이런거죠?

음수 값으로 넣어줘서,,,, 최소값이 맨 위로 올라오게 했는데,,,, 후우

//
//  main.cpp
//  Least_Paht(2)
//
//  Created by yoon tae soo on 05/04/2019.
//  Copyright © 2019 yoon tae soo. All rights reserved.
//

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

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

int V, E;
int K;
int Min_weight[20001];

void Dijstra(int index){
    
    priority_queue<pair<int, int>> pq;
    
    Min_weight[index] = 0;
    pq.push(make_pair(index, 0));
    
    while(!pq.empty()){
        int current = pq.top().first;
        int distance = -pq.top().second;
        
        pq.pop();
        
        if(Min_weight[current] < distance){
            continue;
        }
        else{
            for(int i =0; i<adj[current].size(); i++){
                int item = adj[current][i].first;
                int item_distance = distance + adj[current][i].second;
                
                if(Min_weight[item] == -1){
                    Min_weight[item] = item_distance;
                    pq.push(make_pair(item,-item_distance));
                }
                else if(Min_weight[item] > item_distance){
                    Min_weight[item] = item_distance;
                    pq.push(make_pair(item,-item_distance));
                }
            }
        }
        
    }
    
}

int main(int argc, const char * argv[]) {
    //cin >> V >> E;
    //cin >> K;
    
    scanf("%d %d",&V,&E);
    scanf("%d",&K);
    
    for(int i =1; i<=V; i++){
        Min_weight[i] = -1;
    }
    
    for(int i =0; i< E; i++){
        int u, v, w;
        //cin >> u >> v >> w;
        scanf("%d %d %d",&u,&v,&w);
        adj[u].push_back(make_pair(v, w));
    }
    
    Dijstra(K);
    
    for(int i = 1; i<=V; i++){
        if(Min_weight[i] == -1){
            printf("INF \n");
            //cout << "INF" << endl;
        }
        else{
            printf("%d \n",Min_weight[i]);
        //cout << Min_weight[i] << endl;
        }
    }

    return 0;
}

djm03178 5년 전 1

https://www.acmicpc.net/board/view/34516 5번을 읽어보세요.

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

문제

문제

출처

ICPC

시간초과 해결해주세요 ㅠ ㅠ

yoonfy4280 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말