[bzoj1097][POI2007]旅游景点atr【最短路】【状压dp】

【题目链接】
　　https://www.lydsy.com/JudgeOnline/problem.php?id=1097
【题解】
　　首先预处理出前k+1个点到每个点的最短路。
　　然后状压dp。记f[i][j]$f[i][j]$表示当前停留在i，需要停留的点的状态为j，转移就枚举下一个停留点是哪里。
　　时间复杂度:O(K∗kM+2K∗K)$O(K\ast kM+2^K\ast K)$ 小写k为spfa的常数。

/* --------------
    user Vanisher
    problem bzoj-1097
----------------*/
# include <bits/stdc++.h>
# define    ll      long long
# define    inf     0x3f3f3f3f
# define    M       200010
# define    N       20010
# define    T       20
using namespace std;
int read(){
    int tmp=0, fh=1; char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') fh=-1; ch=getchar();}
    while (ch>='0'&&ch<='9'){tmp=tmp*10+ch-'0'; ch=getchar();}
    return tmp*fh;
}
struct node{
    int data,next,vote;
}e[M*2];
int head[N],dis[T+2][N],f[T+2][1<<T],use[N],place,q[N],n,m,k,ned[T+2];
void build(int u, int v, int w){
    e[++place].data=v; e[place].next=head[u]; head[u]=place; e[place].vote=w;
    e[++place].data=u; e[place].next=head[v]; head[v]=place; e[place].vote=w;
}
void spfa(int id){
    memset(use,0,sizeof(use));
    memset(dis[id],inf,sizeof(dis[id]));
    use[id]=true; dis[id][id]=0;
    int pl=1, pr=1; q[1]=id;
    while (pl<=pr){
        int x=q[(pl++)%n];
        for (int ed=head[x]; ed!=0; ed=e[ed].next)
            if (dis[id][e[ed].data]>dis[id][x]+e[ed].vote){
                dis[id][e[ed].data]=dis[id][x]+e[ed].vote;
                if (use[e[ed].data]==0){
                    use[e[ed].data]=1;
                    q[(++pr)%n]=e[ed].data;
                }
            }
        use[x]=false;
    }
}
int main(){
    n=read(), m=read(), k=read();
    for (int i=1; i<=m; i++){
        int u=read(), v=read(), w=read();
        build(u,v,w);
    } 
    for (int i=1; i<=k+1; i++)
        spfa(i);
    int g=read();
    for (int i=1; i<=g; i++){
        int s=read(), t=read();
        ned[t]=ned[t]+(1<<(s-2));
    }
    if (k==0){
        printf("%d
",dis[1][n]);
        return 0;
    }
    memset(f,inf,sizeof(f));
    for (int i=2; i<=k+1; i++)
        if (ned[i]==0) f[i][1<<(i-2)]=dis[1][i];
    for (int i=0; i<(1<<k); i++)
        for (int j=2; j<=k+1; j++){
            if ((i&(1<<(j-2)))==0) continue;
            for (int t=2; t<=k+1; t++)
                if ((i&(1<<(t-2)))==0){
                    if ((ned[t]&i)==ned[t])
                        f[t][i+(1<<(t-2))]=min(f[t][i+(1<<(t-2))],f[j][i]+dis[j][t]);
                }
        }
    int ans=inf;
    for (int i=2; i<=k+1; i++)
        ans=min(ans,f[i][(1<<k)-1]+dis[i][n]);
    printf("%d
",ans);
    return 0;
}