P3489 [POI2009]WIE-Hexer 题解

一、题目描述:

　　大陆上有 n 个村庄，m 条双向道路，p 种怪物，k 个铁匠，铁匠都在一个村庄里，他可会给你打造他所能打造的所有剑，特定的剑可以对付特定的怪物，每条道路上都可能出现一些特定的怪物，每条道路有一个通过时间。现在要从 1 走到 n，初始的时候你没有剑，要求在经过一条道路的时候，对于任意一种出现在这条道路上的的怪物，你已经有一把特定的剑可以对付他，求从 1 走到 n 的最短时间（打造剑不需要时间）。如果不能到达 n 则输出 -1。数据范围：1<=n<=200，0<=m<=3000，1<=p<=13，0<=k<=n

二、做题思路

　　p这么小，果断状压存状态。设 dp[i][j] 表示走到第 i 个点状态为 j 的最短路，跑一遍 dij 就可以了。（看起来挺简单，实际上我还是写了很久qwq）

三、完整代码：

#include<iostream>
#include<cstring>
#include<queue>
#define N 210
#define M 3010
using namespace std;
int dis[N][(1<<13)+10],ab[N];
int n,m,p,k,u1,v1,w1,s1,t1,n1;
struct EDEG{
    int v,w,gs,nxt;
}e[M*2];
int head[N],cnt;
void add(int u,int v,int w,int gs)
{
    e[++cnt].nxt=head[u];head[u]=cnt;
    e[cnt].v=v;e[cnt].w=w;e[cnt].gs=gs;
}
struct node{
    int val,status,dis;
    bool operator < (const node &t)const{
        return t.dis<dis;
    }
};
priority_queue <node> q;
void dij(int s)
{
    dis[1][0]=0;
    q.push({1,0,0});
    while(!q.empty())
    {
        node tt=q.top();q.pop();
        int u=tt.val,d=tt.status;
        dis[u][d|ab[u]]=dis[u][d];d|=ab[u];
        for(int i=head[u];i!=-1;i=e[i].nxt)
            if((e[i].gs&d)==e[i].gs)
                if(dis[e[i].v][d]>dis[u][d]+e[i].w)
                {
                    dis[e[i].v][d]=dis[u][d]+e[i].w;
                    q.push({e[i].v,d,dis[e[i].v][d]});
                }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>p>>k;
    for(int i=1;i<=k;i++)
    {
        cin>>u1>>s1;
        for(int j=1;j<=s1;j++)
        {
            cin>>v1;
            ab[u1]|=(1<<(v1-1));
        }
    }
    memset(head,-1,sizeof(head));
    memset(dis,0x3f,sizeof(dis));
    for(int i=1;i<=m;i++)
    {
        w1=0;
        cin>>u1>>v1>>t1>>s1;
        for(int j=1;j<=s1;j++)
            cin>>n1,w1|=(1<<(n1-1));
        add(u1,v1,t1,w1);
        add(v1,u1,t1,w1);
    }
    dij(1);
    int minn=1000000000;
    for(int i=0;i<=(1<<13);i++)
        minn=min(minn,dis[n][i]);
    if(minn!=1000000000)
        cout<<minn<<'\n';
    else    cout<<-1<<'\n';
    return 0;
}

　　怎么说，我的代码就是好看qwq。

四、写题心得：

　　今天学了分层图，感觉挺简单的，实际上还是挺考思维的。这个题有点难度又是自己写出来的，所以真的还是很高兴，加油！