普通快乐「CSP多校联考 2019」

题意

给定一个连通图，上面有若干标记点，求这些标记点之间的最短路。保证没有重边和自环。

---

思路

二进制分组一下，按照二进制位将标记点分开。每一组跑一次多源最短路（伪）（其实就是将多个点扔进优先队列跑dijk）。

（数据有点水，分成三组都能过）

代码

#include <bits/stdc++.h>

using namespace std;

namespace StandardIO {

    template<typename T>inline void read (T &x) {
        x=0;T f=1;char c=getchar();
        for (; c<'0'||c>'9'; c=getchar()) if (c=='-') f=-1;
        for (; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
        x*=f;
    }

    template<typename T>inline void write (T x) {
        if (x<0) putchar('-'),x*=-1;
        if (x>=10) write(x/10);
        putchar(x%10+'0');
    }

}

using namespace StandardIO;

namespace Project {

    const int N=100100;
    const int INF=2147483647;

    int n,m,k,ans=INF;
    int cnt;
    int head[N];
    struct node {
        int to,next,val;
    } edge[N<<2];
    int toad[N];
    int dis[N],vis[N];
    struct tst {
        int first,v;
        tst () : first(0),v(0) {}
        tst (int _f,int _v) : first(_f),v(_v) {}
        bool operator < (const tst x) const {
            return v>x.v;
        }
    };
    priority_queue<tst> q;

    inline void add (int a,int b,int c) {
        edge[++cnt].to=b,edge[cnt].val=c,edge[cnt].next=head[a],head[a]=cnt;
    }
    void dijkstra (int x) {
        for (register int i=1; i<=n; ++i) dis[i]=INF,vis[i]=0;
        for (register int i=1; i<=k; ++i) if (toad[i]&(1<<x)) q.push(tst(toad[i],0)),dis[toad[i]]=0,vis[toad[i]]=1;
        while (!q.empty()) {
            tst now=q.top();q.pop();
            for (register int i=head[now.first]; i; i=edge[i].next) {
                int to=edge[i].to;
                if (dis[to]>dis[now.first]+edge[i].val) {
                    dis[to]=dis[now.first]+edge[i].val;
                    if (!vis[to]) vis[to]=1,q.push(tst(to,dis[to]));
                }
            }
        }
        for (register int i=1; i<=k; ++i) if (!(toad[i]&(1<<x))) ans=min(ans,dis[toad[i]]);
    }

    inline void MAIN () {
        read(n),read(m),read(k);
        for (register int i=1,x,y,z; i<=m; ++i) {
            read(x),read(y),read(z);
            add(x,y,z),add(y,x,z);
        }
        for (register int i=1; i<=k; ++i) read(toad[i]);
        for (register int i=0; i<=16; ++i) dijkstra(i);
        write(ans);
    }

}

int main () {
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
    Project::MAIN();
}