글 읽기 - 계속 메모리초과가 납니다 ㅠ

alsyd024 3년 전 0

최단 경로 문제를 풀때와 거의 동일한 다익스트라 코드를 이용했는데 메모리 초과가 납니다 ㅠ

큐가 계속 커질 수 있을 거라는 생각에 검토를 계속 해보는데 이유가 안보이네요...

알려주시면 감사하겠습니다 ㅠ

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, int> ii;
vector<ii> adj[100001];
const long long mod= 1000000009;
ll d[100001];
ll cnt[100001]; 

int main() {
	int n,m,s,e;
	scanf("%d %d %d %d",&n,&m,&s,&e);
	for(int i=0; i<m; i++) {
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);
		adj[a].push_back({(ll)c,b});
		adj[b].push_back({(ll)c,a});
	}
	for(int i=1; i<=n; i++) {
		if(i!=s) d[i]= 1LL<<60;
		else d[i]= 0LL;
	}
	cnt[s]=1LL;
	priority_queue<ii,vector<ii>,greater<ii>> pq;
	pq.push({0LL,s});
	while(!pq.empty()) {
		ii now = pq.top();
		pq.pop();
		if(d[now.second]<now.first) continue;
		for(int i=0; i<adj[now.second].size(); i++) {
			ii next = adj[now.second][i];
			if(d[next.second]>d[now.second]+next.first) {
				d[next.second] = d[now.second]+next.first;
				cnt[next.second] = cnt[now.second];
				pq.push({d[next.second],next.second});
			}
			else if(d[next.second] = d[now.second]+next.first) {
				cnt[next.second]=(cnt[next.second]+cnt[now.second])%mod;
			}
		}
	}
	printf("%lld",cnt[e]);
}

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

문제

문제

출처

ICPC

계속 메모리초과가 납니다 ㅠ

alsyd024 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말