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) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호가 주어진다. |
code>>
#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>
struct Node
{
int Target;
int Distance;
};
std::vector<Node> list[801];
void Dijkstra(std::vector<long long>& distance, int start)
{
std::priority_queue <std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> q;
q.push(std::make_pair(0, start));
distance[start] = 0;
while (!q.empty())
{
auto dis = q.top().first;
auto n = q.top().second;
q.pop();
if (dis > distance[n]) continue;
for (size_t i = 0; i < list[n].size(); i++)
{
if (distance[list[n][i].Target] > dis + list[n][i].Distance)
{
distance[list[n][i].Target] = dis + list[n][i].Distance;
q.push(std::make_pair(distance[list[n][i].Target], list[n][i].Target));
}
}
}
}
int main()
{
std::ios_base::sync_with_stdio(false);
int max, size, start;
std::cin >> max >> size;
for (int i = 0; i < size; i++)
{
Node n;
std::cin >> start >> n.Target >> n.Distance;
Node n1;
n1.Target = start;
n1.Distance = n.Distance;
list[start].push_back(n);
list[n.Target].push_back(n1);
}
int wayPoint1, wayPoint2;
std::cin >> wayPoint1 >> wayPoint2;
std::vector<int> _point = { 1, wayPoint1, wayPoint2 };
std::vector<std::vector<long long>> _distance;
for (int i = 0; i < 3; i++)
{
_distance.push_back(std::vector<long long>(max + 1, 987654321));
Dijkstra(_distance[i], _point[i]);
}
long long sum = std::min(_distance[0][wayPoint1] + _distance[1][wayPoint2] + _distance[2][max], _distance[0][wayPoint2] + _distance[1][max] + _distance[2][wayPoint1]);
printf("%lld\n", sum >= 987654321 ? -1 : sum);
return 0;
}
'알고리즘 > 백준' 카테고리의 다른 글
1463>1로 만들기 (0) | 2018.06.02 |
---|---|
6603>로또 (0) | 2018.05.28 |
1753>최단경로 (0) | 2018.05.19 |
1890>점프 (0) | 2018.05.13 |
10451>순열 사이클 (0) | 2018.05.09 |