[文章目录]
Description
给你n个点，m条边的无向图，请设计一条路线从1出发，到达n，路上访问了K个节点，并且满足一些形如A B（表示访问B之前一定访问过A）的条件。保证A,B属于K个节点之内。当然，你可以途经B节点（并不访问）到达A节点进行访问，然后到达B节点访问。求路线的最短长度N(2<=N<=20000),M(1<=M<=200000),K(0<=K<=20)
K很小啊。限定也只在K个点之间。
预处理出K个点还有1节点到所有点的最短路，（K次堆优化dij）。之后状压DP，dp[s][i]表示已经访问的状态为s，当前在i节点。由此转移。需要特判k为0的情况。时间复杂度其实状压的复杂度完全少于这个。
#include <vector>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[1100000][20];
vector<int>v[22];
int n,m,k,ans=0x7fffffff,d[22][21000];
int head[21000],to[401000],nxt[401000],date[401000],cnt;
inline void add(int x,int y,int z)
{to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; date[cnt]=z;}
struct node
{
int v,dis;
};
bool operator < (node x,node y){return x.dis>y.dis;}
priority_queue<node>he;
void dijkstra(int x,int dis[])
{
memset(dis,0x3f,sizeof (int)*(n+10)); dis[x]=0;
he.push((node){x,0}); int y;
while(he.size())
{
x=he.top().v; y=he.top().dis; he.pop();
if(y>dis[x]) continue;
for(int i=head[x];i;i=nxt[i]) if(dis[to[i]]>y+date[i])
{
dis[to[i]]=y+date[i];
he.push((node){to[i],dis[to[i]]});
}
}
}
bool check(int s,int x)
{
x+=2;
for(int i=0;i!=v[x].size();++i)
if(!(s&(1<<(v[x][i]-2)))) return false;
return true;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
int x,y,z;
for(int i=1;i<=m;++i)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z); add(y,x,z);
}
for(int i=1;i<=k+1;++i)
dijkstra(i,d[i]);
scanf("%d",&z);
while(z--)
{
scanf("%d%d",&x,&y);
v[y].push_back(x);
}
memset(dp,0x3f,sizeof dp);
for(int i=2;i<=k+1;++i) if(!v[i].size()) dp[(1<<(i-2))][i-2]=d[1][i];
for(int s=1;s<(1<<k);++s)
for(int i=0;i<k;++i) if(s&(1<<i))
for(int j=0;j<k;++j) if((s&(1<<j))==0&&check(s,j))
dp[s|(1<<j)][j]=min(dp[s|(1<<j)][j],dp[s][i]+d[i+2][j+2]);
for(int i=0;i<k;++i) ans=min(ans,dp[(1<<k)-1][i]+d[i+2][n]);
if(!k) printf("%d",d[1][n]);
else printf("%d",ans);
return 0;
}