hdu 3832(最短路）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3832

思路：三次spfa求出1，2，3到各点的最短距离，然后枚举中间点到这三点的最短距离之和为ans,最后就是n-ans-1了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 using namespace std;
 7 #define MAXN 222
 8 #define inf 1<<30
 9 struct Node{
10     int x,y,r;
11 }node[MAXN];
12 int n;
13 int map[MAXN][MAXN];
14 bool mark[MAXN];
15 int dd1[MAXN];
16 int dd2[MAXN];
17 int dd3[MAXN];
18 
19 bool Judge(int i,int j){
20     int xx=node[i].x-node[j].x;
21     int yy=node[i].y-node[j].y;
22     if(xx*xx+yy*yy<=(node[i].r+node[j].r)*(node[i].r+node[j].r))
23         return true;
24     return false;
25 }
26 
27 void SPFA(int st,int dd[]){
28     memset(mark,false,sizeof(mark));
29     for(int i=1;i<=n;i++)dd[i]=inf;
30     mark[st]=true;
31     dd[st]=0;
32     queue<int>Q;
33     Q.push(st);
34     while(!Q.empty()){
35         int u=Q.front();
36         Q.pop();
37         mark[u]=false;
38         for(int i=1;i<=n;i++){
39             if(map[u][i]&&dd[i]>dd[u]+map[u][i]){
40                 dd[i]=dd[u]+map[u][i];
41                 if(!mark[i]){
42                     mark[i]=true;
43                     Q.push(i);
44                 }
45             }
46         }
47     }
48 }
49 
50 
51 
52 int main(){
53     int _case;
54     scanf("%d",&_case);
55     while(_case--){
56         scanf("%d",&n);
57         for(int i=1;i<=n;i++){
58             scanf("%d%d%d",&node[i].x,&node[i].y,&node[i].r);
59         }
60         memset(map,0,sizeof(map));
61         for(int i=1;i<=n;i++){
62             for(int j=i+1;j<=n;j++){
63                 if(Judge(i,j))map[i][j]=map[j][i]=1;
64             }
65         }
66         SPFA(1,dd1);
67         SPFA(2,dd2);
68         SPFA(3,dd3);
69         int ans=inf;
70         for(int i=1;i<=n;i++){
71             if(dd1[i]!=inf&&dd2[i]!=inf&&dd3[i]!=inf&&dd1[i]+dd2[i]+dd3[i]<ans){
72                 ans=dd1[i]+dd2[i]+dd3[i];
73             }
74         }
75         if(ans<inf){
76             printf("%d\n",n-ans-1);
77         }else 
78             puts("-1");
79     }
80     return 0;
81 }

View Code