글 읽기 - 질문들 조건 다 맞는것같은데 시간 초과 계속 나네요

vegatrash 5년 전 0

우선순위 큐 pair의 앞부분에 간선의 길이로 정렬하는것도 했고

cin cout도 안썼고

어디가 잘못된건가요?

75퍼에서 자꾸 틀렸다고 나옵니다

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <math.h>
#include <vector>
#include <queue>
#include <list>
#include <time.h>
#include <memory.h>
#include <functional>
#include <utility>
#include <set>
#include <stack>

using namespace std;
typedef pair<int, int> p;

priority_queue<p, vector<p>, greater<p> > pq;
vector<vector<p>> graph(20001);
vector<int> dist(20001, 2e9);

void dijkstra(int start) {
	pq.push({ 0, start });
	dist[start] = 0;

	while (!pq.empty()) {
		
		p now = pq.top();
		pq.pop();

		if (dist[now.second] < now.first) continue;

		for (int i = 0; i < graph[now.second].size(); i++) {
			p next = { graph[now.second][i].first, graph[now.second][i].second };
			if (dist[now.second] + graph[now.second][i].first < dist[next.second]) {
				pq.push(next);
				dist[next.second] = dist[now.second] + graph[now.second][i].first;
			}
		}
	}
	return;
}

int main() {
	int v, e, k;
	scanf("%d %d %d", &v, &e, &k);
	for (int i = 0; i < e; i++) {
		int a, b, w;
		scanf("%d %d %d", &a, &b, &w);
		graph[a].push_back({w, b});
	}

	dijkstra(k);

	for (int i = 1; i <= v; i++) {
		if (dist[i] == 2e9) {
			printf("INF\n");
			continue;
		}
		printf("%d\n", dist[i]);
	}
	return 0;
}

djm03178 5년 전 0

이 코드 그대로 내보니 틀렸다고 안 나오고 '시간 초과'라고 나옵니다. 질문을 올릴 때는 올린 코드가 어떤 판정을 받았는지 정확하게 써 주세요.

질문들 조건이라는 게 혹시 https://www.acmicpc.net/board/view/34516 를 말씀하시는 거라면 4.3을 어기고 있습니다. pq에 무엇을 넣어야 하는지 다시 생각해 보세요.

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

문제

문제

출처

ICPC

질문들 조건 다 맞는것같은데 시간 초과 계속 나네요

vegatrash 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말