[백준 C++] 10473 인간 대포 - 다익스트라

---

 

문제풀이

 

다익스트라 알고리즘을 이용해서 푸는 문제입니다.

각각의 노드 사이의 이동 시간을 구해서 저장해주고 나면

나머지는 일반적인 다익스트라 유형의 문제의 풀이와 동일합니다.

각 노드 사이의 이동 시간을 구할 때 시작 노드를 출발 지점으로 놓으면 도착 지점까지 걸어가는 시간으로 구해야 합니다.

시작 노드를 제외한 나머지 노드에서 출발 할때는 걸어가는 시간과 대포를 이용한 시간 중 작은 값으로 저장해주면 됩니다.

---

코드

cpp

#include <iostream>
#include <list>
#include <cmath>
#include <climits>
#include <queue>
using namespace std;

const double Inf = INT_MAX;

typedef pair<double, double> p;
typedef pair<double, int> n;

int S, E, N;
p Point[102];
list<n> Neighbor[102];

double LS[102];

double Time(bool bRun, p Src, p Dst)
{
‌double DX = Dst.first - Src.first;
‌double DY = Dst.second - Src.second;
‌double D = sqrt(DX * DX + DY * DY);

‌double T = 0;
‌if (bRun)
‌{
‌‌T = D / 5.f;
‌}
‌else
‌{
‌‌T = min(D / 5.f, abs(D - 50.f) / 5.f + 2.f);
‌}

‌return T;
}

void Init()
{
‌cin >> Point[0].first >> Point[0].second;
‌cin >> Point[1].first >> Point[1].second;
‌Neighbor[0].emplace_back(Time(true, Point[0], Point[1]), 1);

‌cin >> N;
‌for (int i = 2; i < N + 2; ++i)
‌{
‌‌cin >> Point[i].first >> Point[i].second;
‌‌Neighbor[0].emplace_back(Time(true, Point[0], Point[i]), i);
‌‌Neighbor[i].emplace_back(Time(false, Point[i], Point[1]), 1);
‌}

‌for (int i = 2; i < N + 1; ++i)
‌{
‌‌for (int j = i + 1; j < N + 2; ++j)
‌‌{
‌‌‌double T = Time(false, Point[i], Point[j]);
‌‌‌Neighbor[i].emplace_back(T, j);
‌‌‌Neighbor[j].emplace_back(T, i);
‌‌}
‌}
}

void Dijkstra()
{
‌for (int i = 0; i < N + 2; ++i)
‌{
‌‌LS[i] = Inf;
‌}
‌LS[0] = 0;

‌priority_queue<n, vector<n>, greater<n>> PQ;
‌PQ.emplace(0, 0);
‌while (!PQ.empty())
‌{
‌‌int Cur = PQ.top().second;
‌‌double T = PQ.top().first;
‌‌PQ.pop();

‌‌if (T > LS[Cur])
‌‌{
‌‌‌continue;
‌‌}

‌‌for (const n& Ngb : Neighbor[Cur])
‌‌{
‌‌‌int Nxt = Ngb.second;
‌‌‌double NT = T + Ngb.first;
‌‌‌if (NT < LS[Nxt])
‌‌‌{
‌‌‌‌LS[Nxt] = NT;
‌‌‌‌PQ.emplace(NT, Nxt);
‌‌‌}
‌‌}
‌}
}

int main()
{
‌ios::sync_with_stdio(false);
‌cin.tie(nullptr); cout.tie(nullptr);

‌Init();
‌Dijkstra();
‌cout << LS[1];
}