Apple Delivery
문제 해석
특정 목장에서 서로 다른 두개의 목장에 사과를 전달할 수 있는 최단경로를 구하는 문제입니다.
설계(5)
전형적인 최단경로 찾기 문제입니다.
시작 지점(PB)에서 사과를 PA1,PA2에 전달하는 방법은 PB->PA1->PA2, PB->PA2->PA1 두가지가 있습니다.
두가지 경로의 최단경로를 구하고 최소값을 출력하면 됩니다.
최단경로를 구하기 위해서 다익스트라 알고리즘을 사용하였고, 위의 논리로는 다익스트라 알고리즘을 4번 사용해야 합니다.
그러나, PA1->PA2 와 PA2->PA1의 최단경로비용은 같기 때문에 3번의 다익스트라 알고리즘으로 원하는 값을 얻을 수 있습니다.
다익스트라 알고리즘을 사용하므로 O(3xClogP)=> O(ClogP)의 시간복잡도가 필요하게 됩니다.
구현(15)
코드
#include <iostream>
#include <memory.h>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
#define MAXN 100001
int C, P, PB, PA1, PA2;
vector<pair<int, ll> > adj[MAXN];
ll dist[MAXN];
ll dijk(int s, int e) {
memset(dist, -1, sizeof(dist));
priority_queue<pair<ll, int> > pq;
pq.push({ 0,s });
dist[s] = 0;
while (!pq.empty()) {
ll cur_dist = -pq.top().first;
int cur = pq.top().second;
pq.pop();
if (cur == e) {
return cur_dist;
}
if (cur_dist != dist[cur]) continue;
for (int i = 0; i < adj[cur].size(); i++) {
int next = adj[cur][i].first;
ll next_dist = cur_dist + adj[cur][i].second;
if (dist[next] == -1 || dist[next] > next_dist) {
dist[next] = next_dist;
pq.push({ -next_dist,next });
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> C >> P >> PB >> PA1 >> PA2;
for (int i = 0; i < C; i++) {
int u, v;
ll d;
cin >> u >> v >> d;
adj[u].push_back({ v,d });
adj[v].push_back({ u,d });
}
cout << min(dijk(PB, PA1) , dijk(PB, PA2))+dijk(PA1,PA2);
return 0;
}
디버깅
제출결과
112 ms
마무리
전형적인 최단경로 구하기 문제였습니다.