글 읽기 - 시간초과가 걸립니당..........

jerryprk 4년 전 0

75퍼에서 멈추고 시간초과뜨던데

이거는 굳이 상관없고 어느부분에서 이런 결과를 도출하게 하는것일까요...........

20000^2 배열을 사용했었다가 메모리초과임을 인지하구 삭제햇구 pair을 사용햇는데 ㅇㅅㅇ

우선순위 큐를 제대로 이해못한건지 모르겟네요

#ifdef _DEBUG
#include "bits_stdc++.h"
#else
#include "bits/stdc++.h"
#endif
#pragma warning(disable:4996)
using namespace std;
#define MAX 20001
#define INF 2147483647
typedef pair<int, int> Data;
vector <Data> load[MAX];
int p, l;
int start, u, v, w;
int check[MAX];
priority_queue <Data, vector<Data>, greater<Data> > q;
void solve() {
	q.push(Data(0, start));
	check[start] = 0;
	while (!q.empty()) {
		int out = q.top().second; q.pop();
		for (int i = 0; i < load[out].size(); i++) {
			int fst = load[out][i].first;
			int se = load[out][i].second; 
			if (check[se] > fst + check[out]) {
				check[se] = fst + check[out];
				q.push(Data(fst, se));
			}
		}
	}
}
int main() {
#ifdef _CONSOLE
	freopen("input.txt", "r", stdin);
#endif
	scanf("%d %d %d", &p, &l, &start);
	for (int s = 1; s <= p; s++)
		check[s] = INF;
	for (int i = 0; i < l; i++) {
		scanf("%d %d %d", &u, &v, &w);
		load[u].push_back(Data( w, v ));
	}
	solve();
	for (int k = 1; k <= p; k++) {
		if (check[k] == INF)
			printf("INF\n");
		else
			printf("%d\n", check[k]);
	}
}

djm03178 4년 전 0

26번째 줄의 첫 번째 인자를 check[se]로만 주면 통과됩니다.

jerryprk 4년 전 0

아 실로 멍청햇내요

좀더주의깊게보겟습니다 ㅜㅜ 감사합니다

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

문제

문제

출처

ICPC

시간초과가 걸립니당..........

jerryprk 4년 전 0

djm03178 4년 전 0

jerryprk 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말