https://www.acmicpc.net/problem/1504
풀이!!!
다익스트라 알고리즘!
다익스트라를 제대로 구현을 한 상태라면 사실 쉽게 풀 수도 있다. 다익스트라를 4번에서 6번 사용을 한다면 최단거리를 1부터 N까지 V1과 V2를 거치면서 최단거리를 구하면 된다.
이 문제에서 한번 이동했던 정점을 다시 이동할 수 있다는 것은 다익스트라를 여러번 사용할 때 같은 정점을 지나도 된다는 것이지 한번의 다익스트라 안에서 최단거리를 구할 때 같은 정점을 지나는 여러번 지나는 것이 아니다. 사실 V1에서 V2로 가는 최단경로를 갈때 임의의 노드를 두번 거치게 된다면 최단거리가 되지 않을 것이다.
일단 다익스트라 알고리즘을 제대로 구현해야하는데 아래의 포스팅을 보면 도움이 될 것이다!!
https://donggul-godsang.tistory.com/77
문제 알고리즘!!
사실 Vstart-> V1-> V2- >Vend 까지 가는 거리와 Vstart-> V2-> V1-> Vend까지의 거리 중에 최솟값을 구하면 된다. 난 6번의 다익스트라를 사용했는데 Vstart-> V1, V1->V2, V2-> Vend 총 3번과, Vstart->V2, V2-> V1, V1-> Vend 3번으로 총 6번 다익스트라를 이용하여 각각의 거리 더하면 된다.
다만 여기서 한가지 주의해야할 점은 경로가 없을 때는 -1을 출력해야하기 때문에 만약 Vtmp1-> Vtmp2로 가는 경우가 없을 때, 즉 dist배열이 INT_MAX일 때 -1을 출력하고 return하면 된다!
다익스트라를 4번만 사용하는 방법은 아래 포스팅을 참고하면 된다!
https://yabmoons.tistory.com/386
그리고 참고로 노드로 구성되어 있는 그래프를 확인하고 싶을 때는 아래 사이트를 가서 예제를 입력하면 한눈에 확인할 수 있어 문제를 푸는데 큰 도움이 되니 참고하면 좋을 것 같다!!!
https://csacademy.com/app/graph_editor/
소스코드!!
#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#include<queue>
#include<limits.h>
using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역
int V;
vector<pair<int,int>> adj_list[801]; //각 노드들의 인접 리스트를 만듦
int visit_once[801];
priority_queue<pair<int,int>> p1; //priority queue를 이용하여 각 순간마다 최단거리에 있는 노드부터 연산 시작
// 각 노드까지의 최단거리를 저장
vector<int> dijkstra(int start)
{
vector<int>dist(V+1,INT_MAX);
memset(visit_once,0,801*sizeof(int));
dist[start]=0;
p1.push(make_pair(0,start));
while(!p1.empty()){
int cur_dist=-p1.top().first; //정점까지의 거리 중 최단거리, -인 수를 복원
int cur_V=p1.top().second; //정점의 번호
p1.pop();
if(dist[cur_V]<cur_dist) // 지금 꺼낸 것보다 더 짧은 경로가 이미 있다면 지금 꺼낸 것을 무시한다
continue;
for(int i=0;i<adj_list[cur_V].size();i++){
int tmp=adj_list[cur_V][i].first; //인접한 노드들의 정점
int nextDist=cur_dist+adj_list[cur_V][i].second; //첫 노드에서 인접한 노드까지의 거리
if(dist[tmp]>nextDist) //더 짧은 경로를 발견하면 tmp까지의 최단거리를 갱신하고 queue에 넣어줌
{
dist[tmp]=nextDist;
p1.push(make_pair(-nextDist,tmp)); //음수로 바꿔야지 작은 수부터 출력 가능함
}
}
}
return dist;
}
int main() {
int bus;
cin>>V>>bus;
for(int i=0;i<bus;i++)
{
int city1,city2,price;
cin>>city1>>city2>>price;
adj_list[city1].push_back(make_pair(city2,price));
adj_list[city2].push_back(make_pair(city1,price));
}
int mid1,mid2,result=0;
cin>>mid1>>mid2;
int start=1,end=V,min_value1,min_value2;
vector<int> dist;
dist=dijkstra(start); // 시작점부터 v1
if(dist[mid1]==INT_MAX)
{
cout<<-1;
return 0;
}
min_value1=dist[mid1];
dist=dijkstra(mid1); // v1부터 v2까지
if(dist[mid2]==INT_MAX){
cout<<-1;
return 0;
}
min_value1+=dist[mid2];
dist=dijkstra(mid2); //v2부터 마지막까지
if(dist[end]==INT_MAX)
{
cout<<-1;
return 0;
}
min_value1+=dist[end];
dist=dijkstra(start); // 시작점부터 v2
if(dist[mid2]==INT_MAX)
{
cout<<-1;
return 0;
}
min_value2=dist[mid2];
dist=dijkstra(mid2); // v2부터 v1까지
if(dist[mid1]==INT_MAX){
cout<<-1;
return 0;
}
min_value2+=dist[mid1];
dist=dijkstra(mid1); //v1부터 마지막까지
if(dist[end]==INT_MAX)
{
cout<<-1;
return 0;
}
min_value2+=dist[end];
result=min(min_value1,min_value2);
cout<<result;
}
'알고리즘! > Dynamic Programming' 카테고리의 다른 글
[C/C++] 백준 12015: 가장 긴 증가하는 부분 수열2 (O(logn) 알고리즘) (2) | 2023.10.14 |
---|---|
[C/C++] 1562: 계단 수 (2) | 2023.10.11 |
[C/C++] 백준 17404: RGB 거리 2 (0) | 2023.09.28 |
[C/C++] 백준 11444: 피보나치 수 6 (점화식 풀이) (0) | 2023.09.17 |
[C/C++] 백준 11660 구간 합 구하기 5 (이차원 구간 합) (0) | 2023.09.15 |