글 읽기 - 시간복잡도 질문 드립니다.

p_ce1052 3년 전 0

dist[i][j] = i번째 정점을 방문하는데 j개의 간선을 쓸 때 최소거리 라고 정의하고 문제를 풀었는데요

너비우선 탐색으로 최단경로를 구했는데 통과가 되서 질문드립니다.

그냥 너비우선탐색은 O(|V| + |E|)이지만 너비우선탐색으로 최단경로를 구하려고 하면 O(VE)가 소요되지 않나요?

근데 상태가 N^2개로 늘어났으니 O(V^2E)가 되서 시간초과가 날 것 같은데 왜 되는지 알고 싶습니다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef pair<ll,pi> pii;
int start,dest;
vector<pi>graph[1005];
ll dist[1005][1005];
ll unit[1005];
void BFS(){
	queue<int>q;
	q.push(dest);
	while(!q.empty()){
		int cur = q.front();
		q.pop();
		for(pi a : graph[cur]){
			int nxt = a.first;
			if(nxt==dest) continue;
			if(!unit[nxt]){
				unit[nxt] = unit[cur]+1;
				q.push(nxt);
			}
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n,m,k;
	cin>>n>>m>>k>>start>>dest;
	while(m--){
		int a,b,w;
		cin>>a>>b>>w;
		graph[a].push_back(pi(b,w));
		graph[b].push_back(pi(a,w));
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++) dist[i][j] = INT64_MAX;
	}
	BFS();
	dist[start][0] = 0;
	queue<pii>q;
	q.push(pii(dist[start][0],pi(start,0)));
	while(!q.empty()){
		ll d = q.front().first;
		ll cur = q.front().second.first;
		ll used = q.front().second.second;
		q.pop();
		if(d>dist[cur][used]) continue;
		if(used>n-1-unit[cur]) continue;
		
		for(pi a : graph[cur]){
			int nxt = a.first;
			ll w = a.second;
			if(dist[nxt][used+1]> d + w){
				dist[nxt][used+1] = d+w;
				q.push(pii(dist[nxt][used+1],pi(nxt,used+1)));
			}
		}	
	}
	vector<pi>ans;
	for(int i=1; i<=n; i++){
		if(dist[dest][i]!=INT64_MAX) ans.push_back(pi(dist[dest][i],i));
	}
	sort(ans.begin(),ans.end());
	cout<<ans[0].first<<'\n';
	while(k--){
		int p;
		cin>>p;
		for(int i=0; i<ans.size(); i++) ans[i].first+=ans[i].second*p;
		sort(ans.begin(),ans.end());
		cout<<ans[0].first<<'\n';
	}
}

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

문제

문제

출처

ICPC

시간복잡도 질문 드립니다.

p_ce1052 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말