글 읽기 - 이렇게하면 왜 시간초과가 날까요?

p_ce1052 3년 전 0

dp인거 보고 풀긴 했는데 아래 코드처럼

(정점 번호, 방문한 날) 을 하나의 노드로 해서 100만개의 노드에 대해 간선 가중치 부호 뒤집고 다익스트라로 최장경로를 구하려 했습니다

시간복잡도가 O(VlogE)로 돌아가야되는데 왜 시간초과가 날까요? 100만 * log100만이면 1초 내에 돌아가지 않나요? 변수가 3개라 3이 곱해져서 그런가요?

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef pair<ll,pi> pii;

vector<pi>graph[1005];
ll dist[1005][1005];
ll arr[1005];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n,m,c;
	cin>>n>>m>>c;
	for(int i=1; i<=n; i++) cin>>arr[i];
	while(m--){
		int a,b;
		cin>>a>>b;
		graph[a].push_back(pi(b,-arr[b]));
	}
	ll ans = 0;
	priority_queue<pii,vector<pii>,greater<pii> >pq;
	for(int i=1; i<=n; i++){
		for(int j=0; j<=1000; j++) dist[i][j] = 1;
	}
	dist[1][0] = 0;
	pq.push(pii(0,pi(1,0)));
	while(!pq.empty()){
		ll d = pq.top().first;
		int cur = pq.top().second.first;
		int day = pq.top().second.second;
		pq.pop();
		if(day==1000) continue;
		if(dist[cur][day]<d) continue;
		for(pi a : graph[cur]){
			int nxt = a.first;
			ll dd = d+a.second;
			if(dist[nxt][day+1]>dd){
				dist[nxt][day+1] = dd;
				pq.push(pii(dd,pi(nxt,day+1)));
			}
		}
	}
	for(int i=0; i<=1000; i++){
		ll earn = -dist[1][i];
		ll used = c*i*i;
		ans = max(ans,earn-used);
	}
	cout<<ans;
}

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

문제

문제

출처

ICPC

이렇게하면 왜 시간초과가 날까요?

p_ce1052 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말