[10473번] 인간 대포

문제 출처 :

https://www.acmicpc.net/problem/10473

알고리즘 분석 :

문제 해결에 필요한 사항

1. 다익스트라 알고리즘

2. 그래프 구성

이 문제는 그래프만 잘 형성하면 쉽게 풀 수 있는 문제이다.

우선 최단 시간을 구하라 하였으니 우리는 거리와 속도를 이용하여 시간을 구한다.

(시간 = 거리 / 속도)

그리고 시작점과 대포와 끝점 사이에 모든 간선을 형성해주고, 그래프를 만들어준다.

(간선의 정보는 시간이 들어가도록 하면 될 것이다.)

이렇게 형성된 그래프를 이용하여 다익스트라 알고리즘을 이용하면 문제를 해결 할 수 있다.

코드 내에 간단하게 주석을 달아두었다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <queue> #include <vector> #include <functional>   using namespace std;   typedef pair<double, double> pdd; typedef pair<int, double> pid; typedef pair<double, int> pdi;   const double INF = 987654321.0;   double getDist(pdd s, pdd e) {     return sqrt((e.first - s.first) * (e.first - s.first)          + (e.second - s.second) * (e.second - s.second)); }   vector<pid> adj[111]; pdd arr[111]; double dist[111];   int main() {     pdd start, end;     scanf("%lf %lf", &start.first, &start.second);     scanf("%lf %lf", &end.first, &end.second);       int n;     scanf("%d", &n);       for (int i = 1; i <= n; i++)         scanf("%lf %lf", &arr[i].first, &arr[i].second);       // 시작점에서 각 대포로의 그래프 형성     for (int i = 1; i <= n; i++)         adj[0].push_back({ i, getDist(start, arr[i]) / 5.0 });       // 시작점에서 끝점으로의 그래프 형성     adj[0].push_back({ n + 1, getDist(start, end) / 5.0 });       // 각 대포에서 끝점으로의 그래프 형성     for (int i = 1; i <= n; i++)     {         adj[i].push_back({ n + 1, getDist(arr[i], end) / 5.0 });         adj[i].push_back({ n + 1, 2.0 + fabs(getDist(arr[i], end) - 50.0) / 5.0 });     }       // 각 대포끼리의 그래프 형성     for (int i = 1; i <= n; i++)         for (int j = 1; j <= n; j++)             if (i != j)             {                 adj[i].push_back({ j, getDist(arr[i], arr[j]) / 5.0 });                 adj[i].push_back({ j, 2.0 + fabs(getDist(arr[i], arr[j]) - 50.0) / 5.0 });             }       // Priority Queue Dijkstra     for (int i = 0; i <= n + 1; i++)         dist[i] = INF;       priority_queue<pdi, vector<pdi>, greater<pdi> > pq;       pq.push({ 0.0, 0 });       while (!pq.empty())     {         int here = pq.top().second;         double hereCost = pq.top().first;           pq.pop();           if (hereCost > dist[here])             continue;             int len = adj[here].size();         for (int i = 0; i < len; i++)         {             int next = adj[here][i].first;             double nextCost = adj[here][i].second + hereCost;               if (nextCost < dist[next])             {                 dist[next] = nextCost;                 pq.push({ nextCost, next });             }         }     }       printf("%.6lf", dist[n + 1]);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus