二分+最短路 uvalive 3270 Simplified GSM Network(推荐)-白红宇

二分+最短路 uvalive 3270 Simplified GSM Network(推荐)

阅读量：5264 次

发布时间：2019-06-14

本文共 2446 字，大约阅读时间需要 8 分钟。

1 // 二分+最短路 uvalive 3270 Simplified GSM Network(推荐)  2 // 题意：已知B（1≤B≤50）个信号站和C（1≤C≤50）座城市的坐标，坐标的绝对值不大于1000，每个城市使用最近的信号站。给定R（1≤R≤250）条连接城市线路的描述和Q（1≤Q≤10）个查询，求相应两城市间通信时最少需要转换信号站的次数。  3 // 思路：建议先阅读 NOI论文 <
     <计算几何中的二分思想>
      >  4 // 直接献上题解吧：  5 // 二分！  6 // l的两端点所属信号站相同：w[l]=0。  7 // 否则若|l|
      
        14 #include 
       
         15 #include 
        
          16 #include 
         
           17 #include 
          
            18 #include 
           
             19 #include 
             20 #include 
             
               21 using namespace std; 22 #define LL long long 23 typedef pair
              
                pii; 24 const int inf = 0x3f3f3f3f; 25 const int MOD = 998244353; 26 const int N = 1020; 27 const int maxx = 200010; 28 #define clc(a,b) memset(a,b,sizeof(a)) 29 const double eps = 1e-8; 30 void fre() {freopen("in.txt","r",stdin);} 31 void freout() {freopen("out.txt","w",stdout);} 32 inline int read() { int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') { if(ch=='-') f=-1; ch=getchar();}while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}return x*f;} 33 struct Point{ 34 double x,y; 35 Point(){} 36 Point(double _x,double _y){ 37 x = _x;y = _y; 38 } 39 Point operator -(const Point &b)const{ 40 return Point(x - b.x,y - b.y); 41 } 42 double operator ^(const Point &b)const{ 43 return x*b.y - y*b.x; 44 } 45 double operator *(const Point &b)const{ 46 return x*b.x + y*b.y; 47 } 48 }b[55],c[55]; 49 int B,C,n,q; 50 51 struct node{ 52 int v,c; 53 node(int vv,int cc){ 54 v=vv; 55 c=cc; 56 } 57 node(){} 58 bool operator <(const node &r) const{ 59 return c>r.c; 60 } 61 }; 62 63 struct edge{ 64 int v,cost; 65 edge(int vv=0,int ccost =0):v(vv),cost(ccost){} 66 }; 67 68 vector
               
                e[N]; 69 bool vis[N]; 70 int dist[N]; 71 void dij(int start){ 72 clc(vis,false); 73 for(int i=0;i<=n+1;i++) dist[i]=inf; 74 priority_queue
                
                 q; 75 while(!q.empty()) q.pop(); 76 dist[start]=0; 77 q.push(node(start,0)); 78 node tmp; 79 while(!q.empty()){ 80 tmp=q.top(); 81 q.pop(); 82 int u=tmp.v; 83 if(vis[u]) continue; 84 vis[u]=true; 85 for(int i=0;i
                 
                  dist[u]+cost){ 89 dist[v]=dist[u]+cost; 90 q.push(node(v,dist[v])); 91 } 92 } 93 } 94 } 95 void add(int u,int v,int w){ 96 e[u].push_back(edge(v,w)); 97 } 98 99 double dis(Point a,Point b){100 return sqrt((a-b)*(a-b));101 }102 103 int belong(Point a){104 double len=(double)inf;105 int num;106 for(int i=1;i<=B;i++){107 if(dis(a,b[i])
                  
                   =inf) printf("Impossible\n");147 else printf("%d\n",dist[v]);148 }149 }150 return 0;151 }