188. [USACO Oct08] 被破坏的电力系统

★☆   输入文件：pwrfail.in   输出文件：pwrfail.out   简单对比
时间限制：3 s   内存限制：128 MB 一场邪恶的暴风雨毁坏了农夫约翰的输电网中的一些电线！农夫约翰有一张包含了所有n（2<=n<=1000）个电能中转点的地图，这些 点被很自然而方便的标识为1..n，并且被整数坐标x_i，y_i（-100000<=x_i<=100000;-100000& lt;=y_i<=100000）定位于坐标系。 有w（1<=w<=10000）条电线仍然保存着没被暴风雨破坏，每条电线连接着两个电能中转点pi,pj（1<=pi<=n;1<=pj<=n）。 他希望从第一个电能中转点把电导入第n个（可能通过一些中间的电能中转点，应当有一组电线连接1和n）。 给出n个电能中转点的坐标和幸存的电线，请确定最少需要架设的电线总长度，但请注意，架设过程中，对于单条电线而言，其长度不应超过m（0.0<=m<=200000.0） 给出一个例子，在下面，左边是一个包含9个电能中转电和3条幸存电线的地图。在这个任务中，规定名。m=2.0。最佳的架设方案是连接6和4，以及6和9。 After the storm Optimally reconnected 3 . . . 7 9 . . . . . 3 . . . 7 9 . . . . . / 2 . . 5 6 . . . . . . 2 . . 5 6 . . . . . . / 1 2-3-4 . 8 . . . . . 1 2-3-4 . 8 . . . . . | | 0 1 . . . . . . . . . 0 1 . . . . . . . . . 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 这是的总长度是 1.414213562 + 1.414213562 = 2.828427124 . 分数：350 题目名称：pwrfail 输入格式：

• 第一行：两个用空格隔开的整数 n和w
• 第二行：一个实数：m
• 第3..n+2：每一行包含两个用空格隔开的整数：x_i和y_i
• 第n+3..n+2+w行：两个空格隔开的整数：pi和pj

输入样例（file pwrfail）： 9 3 2.0 0 0 0 1 1 1 2 1 2 2 3 2 3 3 4 1 4 3 1 2 2 3 3 4 输入说明： 就像图表中说的那样。 输出格式： 第一行：一个整数，实际结果乘以1000后取整。请不要进行任何的4舍5入工作。 输出样例（file pwrfail.out）： 2828 注意计算距离时数据会溢出使用long long然后缩点后SPFA
#include #include #include #include using namespace std; #define INF 999999999.0 #define MAX_N 1010 #define DIS(a,b) sqrt((pos[a].x-pos[b].x)*(long long)(pos[a].x-pos[b].x)+(pos[a].y-pos[b].y)*(long long)(pos[a].y-pos[b].y)) struct POS { int x,y; } pos[MAX_N]; struct FLAG { int V[MAX_N]; int cnt; } Flag[MAX_N]; int n,w; double m; bool road[MAX_N][MAX_N]; double dis[MAX_N][MAX_N]; double d[MAX_N][MAX_N]; double sd[MAX_N]; bool vis[MAX_N]; int sID,tID; void dfs(int v,int flagID) { if(v==0) sID=flagID; else if(v==n-1) tID=flagID; vis[v]=true; Flag[flagID].V[Flag[flagID].cnt++]=v; for(int i=0;isd[q]+d[q][u]) { sd[u]=sd[q]+d[q][u]; if(inq[u]) continue; queue[rear]=u; ADD(rear); inq[u]=true; } } } return sd[tID]; } int main() { freopen("pwrfail.in","r",stdin); freopen("pwrfail.out","w",stdout); scanf("%d%d",&n,&w); scanf("%lf",&m); for(int i=0;i