글 읽기 - 메모리초과

g12359 2년 전 0

다른 코드들을 보면 pair와 우선순위 queue를 사용하던대, 정점의 최댓값 : 20001의 case가 있다는 점에서 배열과 메모리사용량이 다르지 않다고 생각합니다.

단순히 배열을 사용하는 것과 pair를 통한 우선순위 queue의 사용과 어떤 점에서 다른 지 궁금합니다!

#include<iostream>]
#include<cstdio>
#include<vector>
#define INF 100000000
int arr[20001][20001];
using namespace std;
int main() {
    int n, m, k;
    cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n;j++) {
			arr[i][j] = INF;
		}
	}
    for (int i = 0,r,c, v; i < m; i++) {
        cin >> r >> c >> v;
		if(arr[r][c] > v){
        arr[r][c] = v;
		}
    }
	int start = k;
	bool visit[20001];
	int d[20001];
	//==============================================
	for (int i = 1; i <= n;i++) {
		d[i] = arr[start][i];
	}
	visit[start] = true;
	for (int i = 1, cur; i <= n - 2; i++) {
		cur = 0;
		for (int j = 1, min = INF; j <= n; j++) {
			if (d[j] < min && !visit[j]) {
				min = d[j];
				cur = j;
			}
		}
		visit[cur] = true;
		for (int k = 1; k <= n;k++) {
			if (!visit[k] && d[k] > d[cur] + arr[cur][k]) {
				d[k] = d[cur] + arr[cur][k];
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (d[i] == INF) {
			if (i == k)
				cout << "0";
			else
				cout << "INF";
		}
		else {
			cout << d[i];
		}
		cout << endl;
	}
	return 0;   
}

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

문제

문제

출처

ICPC

메모리초과

g12359 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말