[백준] 1054번: 특정한 최단 경로

 

방향성이 없는 그래프에서 1번 정점에서 N번 정점으로 가되 반드시 V1,V2 정점을 지나는 최단 거리를 구하는 문제였습니다.출발 지점과 도착지점은 1번 정점과 N번 정점으로 고정되어 있으므로

 

1 - V1 - V2 - N

1 - V2 - V1 - N

 

이 두 가지 경우만 체크하면 문제에서 요구하는 최단 거리를 구할 수 있습니다.

 

정점과 간선의 최대 개수를 감안하여 시간 복잡도 O(|V|*log|E|)인 다익스트라 알고리즘을 사용했습니다.

 

그래프는 이중벡터를 사용해 인접리스트 형태로 구현했고 

 

최단거리의 합이 가능한 최대값을 넘거나 INF의 합으로 인해 오버플로우 될 경우를 생각하여 조건문을 작성했습니다.

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

const int MAX=800 + 1;
const int INF=987654321;

int N,E,v1,v2,dist[MAX],ans;

vector<vector<pii>> adj_list;

int djikstra(int s,int e){

	fill(dist,dist+N+1,INF);
	dist[s]=0;
    
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	pq.push({0,s});
    
	while(!pq.empty()){
		int cur_node=pq.top().second;
		int cost=pq.top().first;
		pq.pop();
		if(dist[cur_node]<cost) continue;
        
		for(int i=0;i<adj_list[cur_node].size();i++){
			int next_node=adj_list[cur_node][i].second;
			int tmp_cost=cost+adj_list[cur_node][i].first;

			if(tmp_cost<dist[next_node]){
				dist[next_node]=tmp_cost;
				pq.push({tmp_cost,next_node});
			}
		}
	}
    
	return dist[e];
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    
	cin>>N>>E;
    
	adj_list.resize(N+1);
    
	for(int i=0;i<E;i++){
		int a,b,c;
		cin>>a>>b>>c;
		adj_list[a].push_back({c,b});
		adj_list[b].push_back({c,a});
	}
   
	cin>>v1>>v2;
    
	ans=min(djikstra(1,v1)+djikstra(v1,v2)+djikstra(v2,N),djikstra(1,v2)+djikstra(v2,v1)+djikstra(v1,N));
	
    cout<<(ans>3*800*1000||ans<0?-1:ans)<<"\n";
	
	return 0;
}

부족한 부분, 궁금한 점 언제든 댓글 부탁드립니다!