Rday22

Rday22

最小生成树 + CTF入门

P1111 修复公路

题目背景
AA地区在地震过后,连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。

题目描述
给出A地区的村庄数NN,和公路数MM,公路是双向的。并告诉你每条公路的连着哪两个村庄,并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车,即最早什么时候任意两条村庄都存在至少一条修复完成的道路(可以由多条公路连成一条道路)

输入格式
第11行两个正整数N,MN,M

下面MM行,每行33个正整数x, y, tx,y,t,告诉你这条公路连着x,yx,y两个村庄,在时间t时能修复完成这条公路。

输出格式
如果全部公路修复完毕仍然存在两个村庄无法通车,则输出-1−1,否则输出最早什么时候任意两个村庄能够通车。

input

1
2
3
4
5
4 4
1 2 6
1 3 4
1 4 5
4 2 3

output

1
5

Note

1
2
N<=1000,M<=100000
x<=N,y<=N,t<=100000

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pr pair<int,int>
using namespace std;
typedef long long ll;

const int maxx = 5005;

struct node{
ll x, y;
}No[maxx];


bool vis[maxx];
double d[maxx];
int n;

double dis(int i,int j)
{
return sqrt((No[i].x - No[j].x) * (No[i].x - No[j].x) + (No[i].y - No[j].y) * (No[i].y - No[j].y));
}

void prim()
{
for(int i = 1; i <= n; i ++)
d[i] = 1e9;
d[1] = 0.0;
double ans = 0.0;
int id;
double minn;
while(1)
{
id = -1, minn = 1e9;
for(int i = 1; i <= n; i ++)
if(!vis[i] && d[i] < minn)
id = i, minn = d[i];
if(id == -1)
break;
vis[id] = 1;
ans += minn;
for(int i = 1; i <= n; i ++)
{
double tmp = dis(id, i);
if(!vis[i] && d[i] > tmp)
d[i] = tmp;
}
}
printf("%.2f\n", ans);
}

int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++)
scanf("%lld %lld",&No[i].x, &No[i].y);
prim();
return 0;
}

---------------- The End ----------------
0%