글 읽기 - 시간초과.. 어디서나는지 모르겠네요

homs44 2년 전 0

정점 개수만큼 리스트만들고 각 정점에 정점 마다 연결된 간선만 추가해서 graph를 만들고 계산 했는데 시간 초과가 뜹니다.

어디가 잘못된 걸까요?

#include<iostream>
#include<vector>
#include<algorithm>
#include <limits>
#include<queue>

using namespace std;

#define MI numeric_limits<int>::max()

int v,e,k;
vector< vector< pair<int,int> > > graph;
vector<int> weight_map;
vector<bool> visited;



void dijkstra(int k){
    
    weight_map[k-1] = 0;
    queue<int> q;

    q.push(k-1);
    int cur;
    int min_index= -1;
    int min_value= MI;

    while(!q.empty()){
        cur = q.front();
        visited[cur] = true;
        q.pop();
        
        min_index= -1;
        min_value= MI;
        
        int x,y,w;
        for(int j=0,js=(int)graph[cur].size();j<js;j++){
            x = cur;
            y = graph[cur][j].first;
            w = graph[cur][j].second;
            weight_map[y] =min(weight_map[y],weight_map[x]+w);
            
            if(min_value > weight_map[y]&& !visited[y]){
                min_value = weight_map[y];
                min_index = y;
            }
        }
     
        if(min_index!=-1){
            q.push(min_index);
        }
    }
  
}


int main(){
    
    cin >>v>>e;
    cin>>k;
    
    graph.assign(v,vector< pair< int,int> >());
    weight_map.assign(v,MI);
    visited.assign(v,false);
    
    int x,y,w;
    for(int i =0;i<e;i++){
        cin>>x>>y>>w;
        graph[x-1].push_back(make_pair(y-1,w));
    }
    dijkstra(k);
    
    for(int i =0;i<v;i++){
        if(weight_map[i]==MI){
            cout << "INF"<<endl;
        }else{
            cout << weight_map[i]<<endl;
        }
    }
    return 0;
}

djm03178 2년 전 0

다익스트라는 queue가 아니라 priority queue를 사용해야 하는 알고리즘입니다.

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

문제

문제

출처

ICPC

시간초과.. 어디서나는지 모르겠네요

homs44 2년 전 0

djm03178 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말