1504>특정한 최단 경로

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;

}