记录编号	406210	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]在路上	最终得分	100
用户昵称	HZOI_蒟蒻一只	是否通过	通过
代码语言	C++	运行时间	10.242 s
提交时间	2017-05-18 09:04:07	内存使用	208.42 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=20005,maxm=200005,maxk=20;
int N,M,K,Q,head[maxn],dp[25][1<<(maxk+1)],tot,dis[25][maxn],pre[maxk+5];
bool vis[maxn];
struct node
{
	int from,to,next,wei;
}edge[maxm<<1];
void addedge(int u,int v,int w)
{
	edge[++tot].from=u;edge[tot].to=v;edge[tot].wei=w;
	edge[tot].next=head[u];head[u]=tot;
	u^=v^=u^=v;
	edge[++tot].from=u;edge[tot].to=v;edge[tot].wei=w;
	edge[tot].next=head[u];head[u]=tot;
}
struct dij
{
	int dis,num;
	bool operator <(const dij& b)const
	{
		return dis>b.dis;
	}
};
priority_queue<dij>q;
void Dijkstra(int s)
{
	memset(dis[s],0x7f/2,sizeof(dis[s]));
	dis[s][s]=0;
	memset(vis,0,sizeof(vis));
	q.push((dij){0,s});
	while(!q.empty())
	{
		dij x=q.top();q.pop();
		int u=x.num;
		if(vis[u])continue;
		vis[u]=1;
		for(int i=head[u];i;i=edge[i].next)
		{
			int v=edge[i].to;
			if(dis[s][v]>dis[s][u]+edge[i].wei)
			{
				dis[s][v]=edge[i].wei+dis[s][u];
				q.push((dij){dis[s][v],v});
			}
		}
	}
}
void go(int i,int j)
{
	if( (pre[i]&j)!=pre[i] )
	{
		dp[i][j]=0x7f7f7f7f/3;
		return;
	}
	if(j==(1<<(i-1) ) )
	{
		dp[i][j]=0;
		return;
	}
	if(!(j&(1<<(i-1) ) ) )
	{
		dp[i][j]=0x7f7f7f7f/3;
		return;
	}
	if(dp[i][j]!=-1)return;
	dp[i][j]=0x7f7f7f7f/3;
	for(int k=1;k<=K;k++)
	{
		if(i==k||!(j&(1<<(k-1) ) ) )continue;
		go(k,j^(1<<(i-1) ) );
		dp[i][j]=min(dp[i][j],dp[k][j^(1<<(i-1) )]+dis[k][i]);
	}
}
int haha()
{
	freopen("atr.in","r",stdin);
	freopen("atr.out","w",stdout);
	scanf("%d%d%d",&N,&M,&K);K++;
	for(int i=1;i<=M;i++)
	{
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		addedge(x,y,z);
	}
	scanf("%d",&Q);
	for(int i=1;i<=Q;i++)
	{
		int x,y;scanf("%d%d",&x,&y);
		pre[y]|=(1<<(x-1) );
	}
	for(int i=1;i<=K;i++)
	{
		Dijkstra(i);
		if(i!=1)pre[i]|=1;
	}
	memset(dp,-1,sizeof(dp));
	int ans=0x7f7f7f7f/3;
	for(int i=1;i<=K;i++)
	{
		go(i,(1<<K)-1);
		ans=min(ans,dp[i][(1<<K)-1]+dis[i][N]);
	}
	if(K==1)ans=dis[1][N];
	printf("%d\n",ans);
}
int erbiwangxu=haha();
int main(){;}