Участник:Andriygav/DAVIDG

Материал из DISCOPAL
Перейти к: навигация, поиск
  • компилятор: gcc 8.3
#include <cmath>
#include <iostream>
using namespace std;
 
pair<int, int> a[1003];
double d[1003];
 
double dist(int c, int b){
    double x = a[c].first - a[b].first;
    x = (x*x);
    double y = a[c].second - a[b].second;
    y = (y*y);
    double ans = sqrt(x + y);
    return ans;
}
 
int main(){
    int T;
    cin >> T;
    for(int t = 1; t <= T; t++){
        int n, cost;
        cin >> n >> cost;
 
        for(int i = 1 ; i <= n; i++){
            int j, k;
            cin >> j >> k;
            a[i] = make_pair(j, k);
        }
 
        for(int i = 1; i <= n; i++){
            d[i] = 1000000000;
        }
 
        d[1] = 0;
        long long ans = 0;
        for(int i = 1; i <= n; i++){
 
            int mi = -1;
            for(int j = 1; j <= n; j++){
                if(d[j] != -1 && (mi == -1 || d[j] < d[mi])){
                    mi = j;
                }
            }
 
            ans += ceil(d[mi]*cost);
            ans %= 1000000007;
            for(int j = 1; j <= n; j++){
                if(d[j] == -1 || j == mi){
                    continue;
                }
                d[j] = min(d[j], dist(mi, j));
            }
            d[mi] = -1;
        }
        cout << "Scenario #" << t << ": " << ans << endl;
    }
    return 0;
}