记录编号	403429	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]在路上	最终得分	100
用户昵称	Hzoi_Ivan	是否通过	通过
代码语言	C++	运行时间	2.404 s
提交时间	2017-05-10 11:31:06	内存使用	187.47 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define N 20005
using namespace std;
int e=1,head[N],dis[25][N],n,m,k,a[22];
int bit[23],c[22],f[1<<21][22],ans=0x7fffffff;
bool bo[N];
struct edge{
  int v,w,next;
}ed[800005];
void add(int u,int v,int w)
{
     ed[e].v=v;
     ed[e].w=w;
     ed[e].next=head[u];
     head[u]=e++;
}
void spfa(int x)
{
     queue<int > q;
     for(int i=1;i<=n;i++)dis[x][i]=0x7ffffff;
     dis[x][x]=0;
     bo[x]=1; 
     q.push(x);
     while(!q.empty())
     {
       int y=q.front(); q.pop(); bo[y]=0;
       for(int i=head[y];i;i=ed[i].next)
       {
         int v=ed[i].v;
         if(dis[x][y]+ed[i].w<dis[x][v]){
           dis[x][v]=dis[x][y]+ed[i].w;
           if(!bo[v]){
             bo[v]=1; q.push(v);
           }
         }
       }
     }
     return ;
}
void dp()
{
     f[1][1]=0;
     for(int i=1;i<bit[k+1];i++)
       for(int pos=1;pos<=k+1;pos++)
         if(i&bit[pos-1]&&f[i][pos]!=1061109567)
           for(int j=2;j<=k+1;j++)
             if(!(i&(bit[j-1]))&&((i&c[j])==c[j]))
               f[i|bit[j-1]][j]=min(f[i|bit[j-1]][j],f[i][pos]+dis[pos][j]);
}
int main()
{
	freopen("atr.in","r",stdin);
	freopen("atr.out","w",stdout);
    memset(f,0x3f,sizeof(f));
    bit[0]=1;
    for(int i=1;i<=22;i++) bit[i]=bit[i-1]<<1;
    int aa,bb,cc;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++){
      scanf("%d%d%d",&aa,&bb,&cc);
      add(aa,bb,cc);
      add(bb,aa,cc);
    }
    scanf("%d",&m);
    for(int i=1;i<=k+1;i++)
      c[i]|=1;
    for(int i=1;i<=m;i++)
    {
      scanf("%d%d",&aa,&bb);
      c[bb]|=bit[aa-1];
      c[bb]|=c[aa];
    }
    for(int i=1;i<=k+1;i++)
      spfa(i);
    dp();
    for(int i=1;i<=k+1;i++)
      ans=min(ans,f[bit[k+1]-1][i]+dis[i][n]);
    printf("%d\n",ans);
}