링크
https://www.acmicpc.net/problem/1504
문제
방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.
세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.
입력
첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1)
출력
첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.
예제 입력 및 출력
풀이법
입력으로 들어오는 정점 v1,v2를 무조건 지나야하는데 이를 위해서
1 -> v1 -> v2 -> n 이렇게 가는 방식과 1 -> v2 -> v1 -> n이 방식 모두를 탐색해야한다.
문제에서 무방향 그래프이기 때문에 v1->v2와 v2->v1는 경로가 똑같고
1->v2, 1-> v1, v2->n, v1->n, v1->v2이렇게 5번 탐색을 해서 그중 최솟값을 찾아주었다.
답이 계속 91%에서 틀렸는데 INF를 1e8(10에8제곱)으로 설정했기 때문에 int 오버플로우가 발생하는데 이 예외 처리를 잘 해주지 못해서 많이 틀렸다.
플로이드-와샬 방식도 추가 예정
풀이 코드(C++, 다익스트라)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<list>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
#include<tuple>
#include<functional>
#include<utility>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<complex>
#include<cassert>
#define X first
#define Y second
#define pb push_back
#define MAX 801
#define INF 1e9
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define ffor(i, x) for (int (i) = 0; (i) < (x) ; ++(i))
#define coutln(x) cout << x << '\n'
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
vector <pair<int,int>> adj[MAX]; // 노드들의 정보들을 담는 벡터
int v1,v2; // v1,v2 : 거쳐가야하는 정점
int n,e; // n : 정점의 갯수, e : 간선의 갯수
int n1,n2,n3; // n1 : 1 -> v1까지, n2 : v2->v3까지,
int e1,e3; // e1 : 1 -> v2, e2 : v2 -> v1, e3 : v1 -> n
int dijkstra(int start, int dest){
vector<int> dist(MAX,INF); //최단거리를 저장하는 배열, dist배열 초기화 해준다.
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
pq.push({0, start});
dist[start] = 0;
while(!pq.empty()){
int weight = pq.top().first;
int cur = pq.top().second;
pq.pop();
if(dist[cur] < weight) continue;
if(cur == dest) return dist[cur];
for(int i = 0; i < adj[cur].size(); i++){
int nWeight = adj[cur][i].first;
int next = adj[cur][i].second;
if(dist[next] > nWeight + weight){
dist[next] = nWeight + weight;
pq.push({dist[next], next});
}
}
}
return INF;
}
int main(){
fastio;
cin >> n >> e;
for(int i = 0; i < e; i++){
int a,b,c; cin >> a >> b >> c;
adj[a].pb({c, b});
adj[b].pb({c, a});
}
cin >> v1 >> v2;
n1 = dijkstra(1, v1);
n2 = dijkstra(v1, v2);
n3 = dijkstra(v2, n);
e1 = dijkstra(1, v2);
e3 = dijkstra(v1, n);
// int 오버플로우 처리
if((n1 + n2 + n3 >= INF || n1 + n2 + n3 < 0) || (e1 + n2 + e3 >= INF || e1 + n2 + e3 < 0)){
cout << -1 << "\n";
}
else{
cout << min(n1 + n2 + n3, e1 + n2 + e3) << "\n";
}
return 0;
}플로이드-와샬 풀이
추가 예정
