Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <unordered_map>
- #include <string>
- #include <vector>
- #include <iostream>
- #include <set>
- #include <queue>
- #include "optimization.h"
- #include <math.h>
- #include <unordered_map>
- #include <iomanip>
- using namespace std;
- struct town {
- int x;
- int y;
- };
- int main() {
- vector<tuple<double, int, int>> edges;
- cout.tie(0);
- cin.tie(0);
- ios_base::sync_with_stdio(0);
- int n = readInt();
- // cin >> n;
- vector<town> towns(n);
- for (int i = 0; i < n; i++) {
- // cin >> towns[i].x >> towns[i].y;
- towns[i].x = readInt(); towns[i].y = readInt();
- }
- double answer = 0;
- vector<int> dist(n, INT32_MAX);
- dist[0] = 0;
- vector<bool> mark(n, false);
- for (int i = 0; i < n; i++){
- int cur_v = -1;
- for (int j = 0; j < n; j++){
- if (!mark[j] && (cur_v == -1 || dist[j] < dist[cur_v])) cur_v = j;
- }
- answer += sqrt(dist[cur_v]);
- mark[cur_v] = true;
- for (int k =0; k < n; k++){
- if (!mark[k]){
- dist[k] = min(dist[k], (towns[k].x - towns[cur_v].x) * (towns[k].x - towns[cur_v].x) + (towns[k].y - towns[cur_v].y) * (towns[k].y - towns[cur_v].y));
- }
- }
- }
- // cout << std::setprecision(10) << answer;
- writeDouble(answer, 10);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement