HDU 6166 Senior Pan(多校第九场二进制分组最短路）-白红宇

HDU 6166 Senior Pan(多校第九场二进制分组最短路）

阅读量：6265 次

发布时间：2019-06-22

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

题意：给出n个点和m条有向边（有向边！！！！我还以为是无向查了半天），然后给出K个点，问这k个点中最近的两点的距离

思路：比赛时以为有询问，就直接丢了，然后这题感觉思路很棒，加入把所有点分成起点和终点两部分，然后加个S点和T点与他们

的距离为0，然后跑最短路就可以了，但是这样有可能最近的两个点都在起点或者都在终点，那么就不一定是最短的，所以就有个二进制分组。

考虑每个点的编号的二进制表示，那么对于任何两个点，他们至少有一位二进制不同，那么我们通过枚举二进制的位，当前位为1的作为起点集合，

当前位为2的作为终点集合，通过这样分组，我们就可以确定至少有一次分组任意两点分别在起点和终点。

复杂度O(20*nlogm)

代码：

/** @xigua */#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 #define PI acos(-1)using namespace std;typedef long long ll;typedef double db;const int maxn = 1e5 + 5;const int mod = 1e9 + 7;const int INF = 1e8 + 5;const ll inf = 1e15 + 5;const db eps = 1e-5;int cnt, head[maxn]; ll dis[maxn];struct Edge { int v, next; ll w; //记住这里改顺序下面push进队一定要改！ bool operator < (const Edge &rhs) const { return w > rhs.w; }} e[maxn<<2];void add(int u, int v, int co) { e[cnt].v = v; e[cnt].w = co; e[cnt].next = head[u]; head[u] = cnt++;}void init() { cnt = 0; memset(head, -1, sizeof(head));}void dij(int s, int len) { priority_queue
                 
                   pq; for (int i = 1; i <= len; i++) dis[i] = inf; bool vis[maxn] = {0}; dis[s] = 0; pq.push((Edge){s, 0, 0}); while (!pq.empty()) { Edge tmp = pq.top(); pq.pop(); if (vis[tmp.v]) continue; vis[tmp.v] = 1; for (int i = head[tmp.v]; ~i; i = e[i].next) { Edge u = e[i]; if (dis[u.v] > dis[tmp.v] + u.w) { dis[u.v] = dis[tmp.v] + u.w; pq.push((Edge){u.v, 0, dis[u.v]}); } } }}int a[maxn];int u[maxn], v[maxn], w[maxn];void solve() { int n, m; cin >> n >> m; for (int i = 1; i <= m; i++) { scanf("%d%d%d", u + i, v + i, w + i); } int k; cin >> k; for (int i = 1; i <= k; i++) { scanf("%d", a + i); } ll ans = inf; for (int i = 0; i < 20; i++) { init(); for (int j = 1; j <= m; j++) { add(u[j], v[j], w[j]); // add(v[j], u[j], w[j]); } for (int j = 1; j <= k; j++) { if ((1<

转载于:https://www.cnblogs.com/ost-xg/p/7417862.html

你可能感兴趣的文章