백준 10473 : 인간 대포

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

한 정해진 출발지점에서 특정 도착지점으로 가는 최단 경로이자 각 노드마다 가중치(시간)가 다르므로 다익스트라로

구현할 수 있다.

단 간선이 미리 주어져있지는 않아서 n^2 연산을 통해 모든 정점들을 다 연결하고

조건에 따라

1. 대포를 타고 이동할 것인지(거리가 30m 이상이면 대포를 타는 것이 낫다.)

2. 걸어서 이동할 것인지

계산해 가중치를 설정해주었다. 이 때 대포를 타든 걸어서 가든 정점과 정점을 사이를 이동할때는

일직선으로 이동한다고 가정한다(최소시간)

이렇게 각 정점과 연결된 간선에 대한 설정을 마치면 다익스트라로 최단경로를 구할 수 있다.

나는 vertex[1]을 시작지점, vertex[2]를 도착지점으로 설정해주고 시작하였다.

그런데 이렇게 풀었을 경우 4ms 로 AC 를 받는데 다른 분들은 0ms로 많이 구현하였다..

어떤부분에서 비효율이 발생했는지 찾아봐야하는데.. 잘 못찼겠다.

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

#include <iostream> #include <vector> #include <queue> #include <cmath> #include <iomanip> #define MAX 101 #define INF 1000000000 using namespace std; struct Vertex{ bool isCannon = true; double i, j, dist = INF; vector<pair<double, int>> next; bool operator < (const Vertex &v) const { return dist > v.dist; } }; Vertex vertex[MAX]; double getDist(Vertex v1, Vertex v2){ double dt = sqrt(pow(v1.i-v2.i,2) + pow(v1.j-v2.j,2)); if(dt >= 30 && v1.isCannon){ //cannon return abs(dt-50)/5 + 2; }else{ //walk return dt/5; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); vertex[1].dist = 0; vertex[1].isCannon = false; vertex[2].isCannon = false; cin >> vertex[1].i >> vertex[1].j; cin >> vertex[2].i >> vertex[2].j; int m; cin >> m; for(int i = 3; i <= m+2; i++){ cin >> vertex[i].i >> vertex[i].j; } for(int i = 1; i <= m+2; i++){ for(int j = 1; j <= m+2; j++){ if(i==j) continue; vertex[i].next.push_back(make_pair(getDist(vertex[i], vertex[j]), j)); } } priority_queue<Vertex> pq; pq.push(vertex[1]); while(!pq.empty()){ Vertex curVertex = pq.top(); pq.pop(); for(pair<double, int> pa : curVertex.next){ double w = pa.first; int nIdx = pa.second; if(vertex[nIdx].dist > curVertex.dist + w){ vertex[nIdx].dist = curVertex.dist + w; pq.push(vertex[nIdx]); } } } cout << fixed << setprecision(3) << vertex[2].dist << '\n'; return 0; }