POJ - 2908 Quantum 最短路(dj)+記憶化搜尋

題目連結

題意：有長L的要操作01串nw個，目标01串nw個，長L的操作符串nop個

，第i個操作符串每次使用将花費ci。求每個01串變成對應的目标串所需要的最小花費，若無解則輸出NP。

思路：把每個01串當作一個點，每次通過操作i變成曾經未生成的狀态，就相當于這兩個狀态之間連了一條權值為ci的邊。為求最優解，可以通過記憶化搜尋來擴充狀态，dj來維護解的數組。

#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<iostream>
#include<algorithm>
using namespace std;
#define NUM (1<<20)
#define INF 0x3f3f3f3f
struct node
{
    int num,cost;
    bool operator>(const node& x)const
    {
        return cost>x.cost;
    }
};
int L,nop,nw;
int c[32];
int mul2[21];
string op[32];
string s1,s2;
bool pd[NUM];
int dp[NUM];
queue <int> ans;
int getnum(string s)
{
    int num=0;
    for(int i=L-1;i>=0;--i)
        if(s[i]=='1')
            num+=(1<<(L-1-i));
    return num;
}
void solve(int st,int en)
{
    memset(pd,false,sizeof(pd));
    memset(dp,INF,sizeof(dp));
    priority_queue< node , vector<node> , greater<node> > q;
    int num1,pos;
    node x,y;
    x.num=st;
    x.cost=0;
    dp[st]=0;
    q.push(x);
    while(!q.empty())
    {
        x=q.top();
        q.pop();
        if(x.num==en)
        {
            ans.push(x.cost);
            return ;
        }
        if(pd[x.num])continue ;
        pd[x.num]=true;
        for(int i=0;i<nop;++i)
        {
            num1=0;
            for(int j=0;j<L;++j)
            {
                pos=L-1-j;
                switch(op[i][j])
                {
                    case 'N': num1+=(x.num&mul2[pos]);break;
                    case 'S': num1+=mul2[pos];break;
                    case 'C': break;
                    case 'F': num1+=((x.num+mul2[pos])&mul2[pos]);break;
                    default : break;
                }
            }
            if(dp[num1]>dp[x.num]+c[i]&&!pd[num1])
            {
                y.num=num1;
                y.cost=dp[num1]=dp[x.num]+c[i];
                q.push(y);
            }
        }
    }
    ans.push(-1);
}
int main()
{
    int N;
    scanf("%d",&N);
    int num1,num2;
    mul2[0]=1;
    for(int i=1;i<=20;++i)
        mul2[i]=mul2[i-1]<<1;
    while(N--)
    {
        scanf("%d%d%d",&L,&nop,&nw);
        for(int i=0;i<nop;++i)
        {
            cin>>op[i];
            scanf("%d",&c[i]);
        }
        for(int i=0;i<nw;++i)
        {
            cin>>s1>>s2;
            num1=getnum(s1);num2=getnum(s2);
            solve(num1,num2);
        }
        for(int i=0;i<nw;++i)
        {
            num1=ans.front();
            ans.pop();
            if(num1==-1)
                printf("NP ");
            else
                printf("%d ",num1);
        }
        printf("\n");
    }
}