글 읽기 - c++ 우선순위 큐 사용했는데도 시간초과가 납니다..

sanbonai06 3년 전 0

처음에는 cin cout사용하고 endl도 바꿔봤는데도 안되서 scanf printf로 바꿨는데도 안되서 질문을 올립니다.. 문제가 무엇인지 알려주세요,ㅠㅜㅠㅜ

#include<iostream>
#include<stdio.h>
#include<queue>
#include<vector>
#define MAX_V 20001
#define INF 1e9
using namespace std;
vector<pair<int,int>>adj[MAX_V];
bool visited[MAX_V];
int table[MAX_V];

vector<int> dijkstra(int src,int v)
{
  vector<int> dist(v+1,INF);  //정점의 개수,INF로 초기화
  dist[src]=0;  //시작점 거리 0으로 초기화
  priority_queue<pair<int,int>> pq;
  pq.push(make_pair(0,src));  //우선순위 큐에 삽입
  while(!pq.empty())
  {
    int cost=-pq.top().first;
    int here=pq.top().second;
    pq.pop();
    if(dist[here]<cost) continue;   //지금 꺼낸 것 보다 더 작은 경로를 알고 있다면 건너뜀
    for(int i=0;i<adj[here].size();i++)
    {
      int there=adj[here][i].first;
      int nextDist=cost+adj[here][i].second;
      if(dist[there]>nextDist){
        dist[there]=nextDist;
        pq.push(make_pair(-nextDist,there));
      }
    }
  }
  return dist;
}

int main()
{
  int V,E,start;
  int a,b,c;
  scanf("%d %d",&V,&E);
  scanf("%d",&start);
  for(int i=0;i<E;i++)
  {
  	
    scanf("%d %d %d",&a,&b,&c);
    adj[a].push_back({b,c});  //a에서 b로가는 간선의 가중치가 c라는 의미
  }
  for(int i=1;i<dijkstra(start,V).size();i++)
  {
  	if(dijkstra(start,V)[i]==INF) printf("INF");
    else printf("%d",dijkstra(start, V)[i]);
    cout<<"\n";
  }
}

shg9411 3년 전 0

다익스트라 한번만 호출하시면 됩니다.

코드 다시 살펴보세요.

sanbonai06 3년 전 0

헉 그러네요... 너무너무 감사합니다!!

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

문제

문제

출처

ICPC

c++ 우선순위 큐 사용했는데도 시간초과가 납니다..

sanbonai06 3년 전 0

shg9411 3년 전 0

sanbonai06 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말