题目描述

Description

　　FGD想从成都去上海旅游。在旅途中他希望经过一些城市并在那里欣赏风景，品尝风味小吃或者做其他的有趣的事情。经过这些城市的顺序不是完全随意的，比如说FGD不希望在刚吃过一顿大餐之后立刻去下一个城市登山，而是希望去另外什么地方喝下午茶。幸运的是,FGD的旅程不是既定的，他可以在某些旅行方案之间进行选择。由于FGD非常讨厌乘车的颠簸，他希望在满足他的要求的情况下，旅行的距离尽量短，这样他就有足够的精力来欣赏风景或者是泡MM了^_^.整个城市交通网络包含N个城市以及城市与城市之间的双向道路M条。城市自1至N依次编号，道路亦然。没有从某个城市直接到它自己的道路，两个城市之间最多只有一条道路直接相连，但可以有多条连接两个城市的路径。任意两条道路如果相遇，则相遇点也必然是这N个城市之一，在中途，由于修建了立交桥和下穿隧道
，道路是不会相交的。每条道路都有一个固定长度。在中途，FGD想要经过K(K<=N-2)个城市。成都编号为1，上海编号为N,而FGD想要经过的N个城市编号依次为2,3,…,K+1.举例来说，假设交通网络如下图。FGD想要经过城市2,3,4,5，并且在2停留的时候在3之前，而在4,5停留的时候在3之后。那么最短的旅行方案是1-2-4-3-4-5-8,总长度为19。注意FGD为了从城市2到城市4可以路过城市3,但不在城市3停留。这样就不违反FGD的要求了。并且由于FGD想要走最短的路径，因此这个方案正是FGD需要的。

Input

第一行包含3个整数N(2<=N<=20000),M(1<=M<=200000),K(0<=K<=20),意义如上所述。

Output

只包含一行，包含一个整数，表示最短的旅行距离。

Sample Input

8 15 4
1 2 3
1 3 4
1 4 4
1 6 2
1 7 3
2 3 6
2 4 2
2 5 2
3 4 3
3 6 3
3 8 6
4 5 2
4 8 6
5 7 4
5 8 6
3
2 3
3 4
3 5

Sample Output

19

HINT

上面对应于题目中给出的例子。

题目分析

看到k这么小 那...对不对
f[s][i]代表 经过了状态为s的关键点 最后到达了i关键点
预处理出每两点之间的最短路长度 然后就转移就好了
注意！！！ k可以为0 这时候直接输出dis[1][n]
这题卡堆优化spfa 学习了堆优化dij

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int,int> par;
int read()
{
    int sum=0;
    char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') sum=sum*10+(c-'0'),c=getchar();
    return sum;
}
int n,m,k,f[1<<21][21],tim[21000];
int tot,head[20010],to[400100],net[400100],val[400100],dis[22][20010];
bool vis[20010];
void add(int x,int y,int c) { net[++tot]=head[x],head[x]=tot,to[tot]=y,val[tot]=c; }
void dij(int s)
{
    memset(dis[s],0x3f,sizeof dis[s]);
    memset(vis,0,sizeof vis);
    priority_queue<par>q;
    dis[s][s]=0,q.push(par(0,s));
    while(q.size())
    { 
        int x=q.top().second;
        q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head[x];i;i=net[i])
            if(dis[s][to[i]]>dis[s][x]+val[i])
                dis[s][to[i]]=dis[s][x]+val[i],q.push(par(-dis[s][to[i]],to[i]));
    }
}
int main()
{   
    n=read(),m=read(),k=read();
    for(int x,y,c,i=1;i<=m;i++)
        x=read(),y=read(),c=read(),add(x,y,c),add(y,x,c);
    for(int i=1;i<=k+1;i++) dij(i);
    int pol;
    scanf("%d",&pol);
    for(int x,y,i=1;i<=pol;i++) x=read(),y=read(),tim[y]|=1<<(x-2);
    if(!k) 
    { 
        printf("%d",dis[1][n]);     
        fclose(stdin),fclose(stdout);
        return 0; 
    }
    memset(f,0x3f,sizeof f);
    for(int i=2;i<=k+1;i++) if(!tim[i]) f[1<<(i-2)][i-1]=dis[1][i];
    for(int i=1;i<(1<<k);i++)
        for(int j=2;j<=k+1;j++)
            if(i&(1<<(j-2)))
                for(int z=2;z<=k+1;z++)
                {
                    if(j==z) continue;
                    if(i&(1<<(z-2))) continue;
                    if((~i)&tim[z]) continue;
                    f[i|(1<<(z-2))][z-1]=min(f[i|(1<<(z-2))][z-1],f[i][j-1]+dis[j][z]);
                }
    int ans=1<<30;
    for(int i=2;i<=k+1;i++) ans=min(ans,f[(1<<k)-1][i-1]+dis[i][n]);
    printf("%d",ans); 
    return 0;
}