글 읽기 - 1753번 메모리초과 질문드립니다.

shfur2006 4년 전 0

전체코드가 이러한데 배열서 벡터로바꾸고 해봣음에 초과가나오길래 여쭤봅니다.. 어느부분이 문제일까요 ?

#include <iostream>
#include <queue>
using namespace std;
vector<int> bfs();

int v, e;
int st;
vector<pair<int, int>> graph[20000];
int main() {
	
	cin >> v >> e;
	cin >> st;
	st -= 1;
	int u, p, w;
	for (int i = 0; i < e; ++i) {
		cin >> u >> p >> w;
		
		graph[u-1].push_back(make_pair(p-1, w));
		
	}

	vector<int> an=bfs();

	cout << 0<<endl;
	for (int i = 1; i < v; ++i) {
		if (an[i] == 0) {
			cout << "INF" << endl;
		}else	
			cout << an[i]<< endl;
	}

	getchar();
	getchar();
}
vector<int> bfs() {
	queue<int> q;
	vector<int> an(v,0);

	q.push(st);
	int qs;
	int cur;
	while (!q.empty()) {
		qs=q.size();

		for (int i = 0; i < qs; ++i) {
			cur = q.front();
			q.pop();

			for (int j = 0; j < graph[cur].size(); ++j) {
				int cv = graph[cur].at(j).first;
				q.push(cv);
				if (an[cv] == 0) {
					if (cur == st) {
						an[cv] = graph[cur].at(j).second;
					}
					else {
						an[cv] = graph[cur].at(j).second+an[cur];
					}
				}
				else if (graph[cur].at(j).second + an[cur] < an[cv]) {
					an[cv] = graph[cur].at(j).second;
				}
			}
		}
	}
	return an;
}

soloranker66 4년 전 0

방법 자체가 잘못됬어요. 다익스트라 알고리즘을 사용하셔야합니다.

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

문제

문제

출처

ICPC

1753번 메모리초과 질문드립니다.

shfur2006 4년 전 0

soloranker66 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말