글 읽기 - 시간 초과 질문입니다.

ray5273 5년 전 0

제가 다익스트라를 정확하게 이해 하고 푼건 아닌거같아서

시간초과가 나는것 같은데

어느부분에서 나는지 혹시 알려주실수 있는지 궁금합니다.

#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;


typedef struct Edge{
    int end;
    int distance;
}Edge;


void dijkstra(int *distances,int *visited,vector<Edge> *edges,int V,int index){
  

  for(int i=0;i<V+1;i++){
      distances[i] = INT_MAX;
      visited[i] = false;
  }

  distances[index] = 0;  
  vector<int> adj;

  while(1){
      int visited_num = 0;
      int not_connected = 0;

      for(int i=1;i<=V;i++){
         if(visited[i])
           visited_num++;
         else if(!visited[i] && distances[i] == INT_MAX)
           not_connected++;
      }

      if(visited_num + not_connected == V){
          break;
      }

      int current = -1;
      int minimum_distance = INT_MAX;
     //근처가 비어 있지 않을시 근처중에서 가장 작은걸 쓴다. 
     if(!adj.empty()){
          for(int i=0;i<(int)adj.size();i++){
              if(!visited[ adj[i] ] && minimum_distance > distances[ adj[i] ]){
                  minimum_distance = distances[ adj[i] ];
                  current = adj[i] ; 
              } 
          } 
          adj.clear();
     }else{
          //비어 있을 시 방문하지 않은 점 중 가장 cost가 작은거 쓴다.
          for(int i=1;i<=V;i++){
              if(!visited[i] && minimum_distance > distances[i]){
                  minimum_distance = distances[i];
                  current = i;
              }
          } 
     }
    
    visited[current] = true;  
      
    for(int i=0;i<(int)edges[current].size();i++){
          int end = edges[current][i].end;
          int distance = edges[current][i].distance;
          adj.push_back(end);

          if(distances[end] > distances[current] + distance ){
              distances[end] = distances[current] + distance;
          }
    }
  }


}

int main(){

    int V,E;
    scanf("%d %d",&V,&E);
    int index;
    scanf("%d",&index);
    
    vector<Edge> edges[V+1];
    

    for(int i=0;i<E;i++){
        int u,v,w;
        Edge e;
        scanf("%d %d %d",&u,&v,&w);
        e.end = v;
        e.distance = w;
        edges[u].push_back(e);
    }
  
    int *distances = new int[V+1];
    int *visited = new int[V+1];

    dijkstra(distances,visited,edges,V,index);
    for(int i=1;i<=V;i++){
        if(i==index){
            cout << 0 << endl;
        }else{
          if(distances[i] != INT_MAX)
            cout << distances[i] << endl;
          else
            cout << "INF" << endl;
        }
    }
}

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

문제

문제

출처

ICPC

시간 초과 질문입니다.

ray5273 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말