题面描述:
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, 总长度为 1
9 注意 FGD 为了从城市 2 到城市 4 可以路过城市 3, 但不在城市 3 停留这样就不违反 FGD 的要求了并且由于 FGD 想要
走最短的路径, 因此这个方案正是 FGD 需要的
分析:
发现 n 很大但 k 很小, 考虑把 k 这部分状压
我们先预处理出来前 k+1 个点到所有点的最短路
f[i][j] 表示已经去过的点的状态为 i, 当前站在 j 这个点上的最小代价
转移一下, 不是很难
最后答案要在 f[mask][i]+dis[i][n] 中取 min
代码:
- #include <stdio.h>
- #include <string.h>
- #include <algorithm>
- #include <queue>
- using namespace std;
- #define LL long long
- #define N 20001
- #define M 400001
- #define inf 100000000
- int map[25][25],n,m,K,p;
- int bef[25],dis[22][N];
- int head[N],to[M],nxt[M],cnt,val[M];
- int f[22][1<<20];
- int vis[N];
- inline void add(int u,int v,int w){
- to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;val[cnt]=w;
- }
- void dijkstra(int s){
- priority_queue <pair <int,int> > q;
- for(int i=1;i<=n;i++)dis[s][i]=inf;
- memset(vis,0,sizeof(vis));
- dis[s][s]=0;
- q.push(make_pair(0,s));
- while(!q.empty()){
- int x=q.top().second;q.pop();
- if(vis[x])continue;
- vis[x]=1;
- for(int i=head[x];i;i=nxt[i]){
- if(dis[s][to[i]]>dis[s][x]+val[i]){
- dis[s][to[i]]=dis[s][x]+val[i];
- q.push(make_pair(-dis[s][to[i]],to[i]));
- }
- }
- }//printf("%d\n",dis[s][1]);
- }//g++ a.cpp -o a -g
- int main(){
- int i,j,k;
- scanf("%d%d%d",&n,&m,&K);
- int mask=(1<<K)-1;
- int x,y,z;
- for(i=1;i<=m;i++){
- scanf("%d%d%d",&x,&y,&z);
- add(x,y,z);add(y,x,z);
- }
- for(i=1;i<=K+1;i++)dijkstra(i);
- if(!K){printf("%d\n",dis[1][n]);return 0;}
- scanf("%d",&p);
- for(i=1;i<=p;i++){
- scanf("%d%d",&x,&y);
- bef[y]|=(1<<x-2);
- }
- memset(f,0x3f,sizeof(f));
- for(i=2;i<=K+1;i++)if(!bef[i]){
- f[i][1<<i-2]=dis[1][i];
- }
- for(i=1;i<=mask;i++){
- for(j=2;j<=K+1;j++){
- if((i&(1<<j-2))==0)continue;
- for(k=2;k<=K+1;k++){
- if((bef[k]|i)!=i)continue;
- if(i&(1<<k-2))continue;
- f[k][i|(1<<k-2)]=min(f[k][i|(1<<k-2)],f[j][i]+dis[j][k]);
- }
- }
- }
- int ans=1<<30;
- for(i=2;i<=K+1;i++)ans=min(ans,f[i][mask]+dis[i][n]);
- printf("%d\n",ans);
来源: http://www.bubuko.com/infodetail-2515766.html