Pagini recente » Cod sursa (job #3332594) | Cod sursa (job #3002724) | Cod sursa (job #2968662) | Cod sursa (job #2713251) | Cod sursa (job #3325018)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("retea2.in");
ofstream fout("retea2.out");
const double mare = 100002;
void dijkstra(int start);
double distanta(pair<int, int> a, pair<int, int> b);
struct ura
{
int nod;
double cost;
bool operator < (const ura &aux) const
{
return cost > aux.cost;
}
};
priority_queue<ura> q;
double d[4001], suma;
int n, m;
bool viz[4001];
pair<int, int> coord[4001];
int main()
{
fin>>n>>m;
for(int i = 1; i <= n+m; ++i)
d[i] = mare;
for(int i = 1; i <= n; ++i)//centrale
{
fin>>coord[i].first>>coord[i].second;
d[i] = 0;
q.push({i, 0});
}
for(int i = n+1; i <= n+m; ++i)
{
fin>>coord[i].first>>coord[i].second;
}
dijkstra(1);
fout<<fixed<<setprecision(6)<<suma;
return 0;
}
void dijkstra(int start)
{
while(!q.empty())
{
int nod = q.top().nod;
double crtcost = q.top().cost;
q.pop();
if(viz[nod] || crtcost != d[nod])
continue;
viz[nod] = 1;
suma += crtcost;
for(int i = 1; i <= n+m; ++i)
{
if(viz[i])
continue;
double dist = distanta(coord[nod], coord[i]);
if(d[i] > dist)
{
d[i] = dist;
q.push({i, dist});
}
}
}
}
double distanta(pair<int, int> a, pair<int, int> b)
{
int c1 = (a.first - b.first) * (a.first - b.first);
int c2 = (a.second - b.second) * (a.second - b.second);
return sqrt(c1 + c2);
}