글 읽기 - 80퍼에서 시간초과가 나옵니다. ㅠ

eirc8260 5년 전 0

정석대로 했다고 생각하는데

도대체 왜 시간초과가 나오는지 모르겠네요 ㅠ

#include<iostream>
#include<vector>
#include<queue>
#include<limits.h>
#include<functional>
using namespace std;

typedef pair<int, int> pr; // <Weight, Dest>

class Solution {
private:
	int vNum;
	int eNum;
	int startV;
	vector<vector<pr>> Gp;
public:
	Solution() {
		scanf("%d %d", &vNum, &eNum);
		scanf("%d", &startV);
		Gp.resize(vNum + 1);
		int startP, destP, weight;
		for (int i = 0; i < eNum; i++) {
			scanf("%d %d %d", &startP, &destP, &weight);
			Gp[startP].push_back(make_pair(weight, destP));
		}
	}
	void Dijkstra() {
		vector<int> Distance(vNum + 1, INT_MAX);
		Distance[startV] = 0;
		priority_queue<pr, vector<pr>, greater<pr>> pq; // min pq
		pq.push(make_pair(0, startV));
		int weight, dest;
		while (!pq.empty()) {
			weight = pq.top().first;
			dest = pq.top().second;
			pq.pop();
            
            if(weight > Distance[dest]) continue;
			for (auto p : Gp[dest]) {
				if (Distance[p.second] > Distance[dest] + p.first) {
					Distance[p.second] = Distance[dest] + p.first;
					pq.push(make_pair(p.first, p.second));
				}
			}
		}

		for (int i = 1; i <= vNum; i++) {
			if (Distance[i] == INT_MAX)
				printf("INF\n");
			else
				printf("%d\n", Distance[i]);
		}
		
	}



};


int main(void) {
	Solution Sol;
	Sol.Dijkstra();
	



	return 0;
}

djm03178 5년 전 0

https://www.acmicpc.net/board/...

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

문제

문제

출처

ICPC

80퍼에서 시간초과가 나옵니다. ㅠ

eirc8260 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말