Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- #include <vector>
- #include <algorithm>
- #include <queue>
- using namespace std;
- struct node{
- int index;
- double shortest_path;
- node(int i, double p){
- index = i;
- shortest_path = p;
- }
- bool operator < (const node & tmp)const {
- return shortest_path > tmp.shortest_path;
- }
- };
- int main() {
- int N;
- cin >> N;
- vector<pair<int,int>> kordinati;
- for (int i = 0; i < N; i++) {
- int a,b;
- cin >> a >> b;
- kordinati.push_back(make_pair(a,b));
- }
- vector<pair<int,double>> graph [N];
- for (int i = 0; i < N; i++) {
- for (int j = 0; j < N; j++) {
- double D = sqrt((kordinati[j].first - kordinati[i].first) * (kordinati[j].first - kordinati[i].first) +
- (kordinati[j].second - kordinati[i].second) * (kordinati[j].second - kordinati[i].second));
- if (D<=10){
- graph[i].push_back(make_pair(j,D));
- graph[j].push_back(make_pair(i,D));
- }
- }
- }
- priority_queue<node> pq;
- pq.push(node(0,0));
- vector<bool> vistited (N+1, false);
- vector<double> distance(N + 1, 2e9);
- distance[0] = 0;
- while (!pq.empty()){
- node current = pq.top();
- pq.pop();
- vistited[current.index] = true;
- if(current.index == N-1){
- cout << current.shortest_path << endl;
- break;
- }
- for (int i = 0; i < graph[current.index].size(); i++) {
- int sosed = graph[current.index][i].first;
- double path = graph[current.index][i].second;
- if(!vistited[sosed] and current.shortest_path + path < distance[sosed]){
- pq.push(node(sosed,current.shortest_path + path));
- distance[sosed] = current.shortest_path + path;
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement