Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- #include <cmath>
- using namespace std;
- const int INF = 1e9;
- int N;
- vector<pair<int, int>> systems;
- vector<vector<pair<int, double>>> graph;
- double euclidean_distance(pair<int, int> A, pair<int, int> B) {
- double dx = A.first - B.first;
- double dy = A.second - B.second;
- return sqrt(dx * dx + dy * dy);
- }
- void create_graph() {
- graph.resize(N);
- for (int i = 0; i < N; i++) {
- for (int j = 0; j < N; j++) {
- if (i != j) {
- double weight = euclidean_distance(systems[i], systems[j]);
- if (weight <= 10) {
- graph[i].push_back({j, weight});
- graph[j].push_back({i, weight});
- }
- }
- }
- }
- }
- vector<double> dijkstra(int start) {
- vector<double> dist(N, INF);
- priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;
- dist[start] = 0;
- pq.push({0, start});
- while (!pq.empty()) {
- int node = pq.top().second;
- double curr_dist = pq.top().first;
- pq.pop();
- if (curr_dist > dist[node]) continue;
- for (auto &edge : graph[node]) {
- int neighbor = edge.first;
- double weight = edge.second;
- if (dist[node] + weight < dist[neighbor]) {
- dist[neighbor] = dist[node] + weight;
- pq.push({dist[neighbor], neighbor});
- }
- }
- }
- return dist;
- }
- int main() {
- cin >> N;
- systems.resize(N);
- for (int i = 0; i < N; i++) {
- cin >> systems[i].first >> systems[i].second;
- }
- create_graph();
- vector<double> distances = dijkstra(0);
- double result = distances[N - 1];
- cout.precision(10);
- cout << fixed << result << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement