[Codeforces 100495A][2014 KTU ACM ICPC Qualification Round][Dijkstra] Crystals

原題連結

注意到因為n很小...所以對於任何一個水晶集合都可以將狀態用一個int表示出來(點)，然後將集合的變換看成狀態的轉移(邊)

那麼本題就可以套用經典的最短路算法解決O(NlogN)，此時N=(2^n)
但是值得注意的地方是，因為可以用目前狀態的子集去變換，所以對於狀態S的所有真子集的變換，狀態S都可以拿來用

對應到code上就是檢查每一條邊看看自己能不能用就好，多了這個步驟之後的複雜度會變成O(MNlogN)，對於此題的數據來說還是可以通過的

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL INF=(1LL<<60);
const LL maxn=(1<<12)+5;
struct Edge{LL from,to,w;};
struct HeapNode
{
    LL now,d;
    bool operator < (const HeapNode& rhs) const {return d>rhs.d;}
};
struct Dijkstra
{
    LL n;
    vector<Edge> edges;
    LL done[maxn],d[maxn];
    void init(LL a)
    {
        n=a;
        edges.clear();
    }
    void AddEdge(LL a,LL b,LL c)
    {
        edges.push_back((Edge){a,b,c});
    }
    void dijkstra(LL s)
    {
        for(LL i=0;i<n;i++) d[i]=INF,done[i]=0;
        priority_queue<HeapNode> pq;
        d[s]=0;
        pq.push((HeapNode){s,d[s]});
        while(!pq.empty())
        {
            HeapNode x=pq.top();pq.pop();
            if(done[x.now]) continue;
            done[x.now]=1;
            for(LL i=0;i<edges.size();i++)
            {
                Edge& e=edges[i];
                if((e.from&x.now)!=e.from) continue;
                if(d[e.to|(x.now^e.from)]>d[x.now]+e.w)
                {
                    d[e.to|(x.now^e.from)]=d[x.now]+e.w;
                    pq.push((HeapNode){e.to|(x.now^e.from),d[e.to|(x.now^e.from)]});
                }
            }
        }
    }
}solver;
inline LL getcrystal()
{
    LL ret=0,cnt;
    scanf("%I64d",&cnt);
    for(LL i=0,x;i<cnt;i++) {scanf("%I64d",&x);ret|=(1<<x);}
    return ret;
}
int main()
{
    LL T,kase=0;
    scanf("%I64d",&T);
    while(T--)
    {
        LL n,m,init,final;
        scanf("%I64d%I64d",&n,&m);
        solver.init((1<<n));
        init=getcrystal();final=getcrystal();
        for(LL i=0,a,b,c;i<m;i++)
        {
            scanf("%I64d",&c);
            a=getcrystal();b=getcrystal();
            solver.AddEdge(a,b,c);
        }
        solver.dijkstra(init);
        if(solver.d[final]!=INF) printf("Case #%I64d: YES %I64d\n",++kase,solver.d[final]);
        else printf("Case #%I64d: NO\n",++kase);
    }
}