글 읽기 - 시간초과 이유를 모르겠습니다.

gjdpdms2005 3년 전 0

priority_queue를 사용하여 우선순위도 first가 distance가 되게 했는데 시간초과가 나서 질문 남깁니다!

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

using namespace std;

#define MAX 20001
#define P pair<int, int>
#define INF 1e9

int V, E;
vector<P> graph[MAX];

vector<int> dijkstra(int start){
    vector<int> dist(V+1, INF);
    priority_queue<P> need_visit;
    need_visit.push(make_pair(dist[start]=0, start));

    while(!need_visit.empty()){
        int distance = need_visit.top().first;
        int now = need_visit.top().second;
        need_visit.pop();

        if(dist[now] < distance){
            continue;
        }

        for(int i = 0; i < graph[now].size(); i++){
            int cost = graph[now][i].first + distance;
            int next = graph[now][i].second;

            if(dist[next] > cost){
                need_visit.push(make_pair(dist[next] = cost, next));
            }
        }
    }
    return dist;
}

int main(void){
    cin.tie(NULL), cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin >> V >> E;

    int startVertex;
    cin >> startVertex;

    for(int i = 0; i < E; i++){
        int from, to, value;
        cin >> from >> to >> value;
        graph[from].push_back(make_pair(value, to));
    }

    vector<int> result = dijkstra(startVertex);

    for(int i = 1; i <= V; i++){
        if(result[i] == INF){
            cout << "INF" <<'\n';
        } else {
            cout << result[i] << '\n';
        }
    }
}

3587jjh 3년 전 1

priority queue에서 distance가 가장 작은것부터 뽑아야하는데 지금은 가장 큰 것부터 뽑고있습니다.

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

문제

문제

출처

ICPC

시간초과 이유를 모르겠습니다.

gjdpdms2005 3년 전 0

3587jjh 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말