旅游景点atr-编程日记-博客水木

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需要的。

输入

第一行包含3个整数N(2<=N<=20000),M(1<=M<=200000),K(0<=K<=20),意义如上所述。以下M行，每行包含3个整数X，y，z，(1<=x，y<=n，0<z<=1000)；

接下来一行，包含一个整数q，表示有q个限制条件(0<=q<n)。以下q行，每行两个整数f，l(1<=l，f<=n)，表示在f停留的时候要在l之前。

输出

样例输入

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

样例输出

#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<iostream> #include<queue> #define V 200002 #define INF 1115006 #define S 1<<10+1 typedef long long LL; //#define LL long long using namespace std; int n,m; int k; struct data {int to,dis,next;data(){dis=0; } }Edge[2*V]; queue<int>Q; int head[V],tot,l; LL ff[V]; LL f[23][2100000]; LL find(int); LL dis[21][V],vis[V]; void spfa(int); void addedge(int,int,int); LL dfs(int); LL ans; void init(); int main() {memset(head,-1,sizeof(head));// freopen("atr.in","r",stdin);freopen("atr.out","w",stdout);//freopen(&#","r",stdin);freopen(&#","w",stdout);scanf("%d%d%d",&n,&m,&k);int x,y,z,xx,yy; init();for(int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z); x--;y--;addedge(x,y,z);addedge(y,x,z); }// while(1);for(int i=0;i<=k;i++){spfa(i); }//while(1);int q,ww=0;scanf("%d",&q);int u,o;for(int i=1;i<=q;i++){scanf("%d%d",&u,&l);u--;l--;if(u>k||l>k)continue;ff[l]|=(1<<(u)); }int a,b,c;for(int i=1;i<=k;i++){ff[i]|=(1<<0); //cout<<ff[i]<<" @ "<<i<<endl;}memset(f,1,sizeof(f));//memset(vis,0,sizeof(vis));//cout<<dfs(1);f[0][0]=0;f[0][1]=0;for(int i=0;i<(1<<(k+1));i++){for(int j=0;j<=k;j++) if((ff[j]&i)==ff[j]&&((1<<j)&i)==0) for(int e=0;e<=k;e++)if(((1<<e)&i)){f[j][((1<<j)|i)]=min(f[j][((1<<j)|i)],f[e][i]+dis[e][j]); // cout<<" !!!dis"<<dis[e][j]<<" !! "<<j<<" "<<i<<" "<<f[j][i]<<" "<<ff[j]<<" "<<(ff[j]&i)<<" "<<((1<<j)&i)<<endl; } // for(int j=0;j<=k;j++)//cout<<j<<" "<<i<<" "<<f[j][i]<<" "<<ff[j]<<" "<<(ff[j]&i)<<" "<<((1<<j)&i)<<endl; }ans=500000005;for(int i=0;i<=k;i++){ans=min(ans,f[i][(1<<(k+1))-1]+dis[i][n-1]); //cout<<f[i][(1<<k)-1]<<" "<<i<<endl;}cout<<ans<<endl;return 0; } void init() {memset(head,-1,sizeof(head));memset(dis,1,sizeof(dis)); } void addedge(int x,int y,int z) {Edge[tot].to=y;Edge[tot].dis=z;Edge[tot].next=head[x];head[x]=tot++; } void spfa(int x) {memset(vis,0,sizeof(vis));int v,z;//memset(dis[x],1,sizeof(dis[x]));vis[x]=1;dis[x][x]=0;while(!Q.empty())Q.pop();Q.push(x);while(!Q.empty()){v=Q.front(); for(int i=head[v];i!=-1;i=Edge[i].next){z=Edge[i].to; if(dis[x][z]>dis[x][v]+Edge[i].dis){dis[x][z]=dis[x][v]+Edge[i].dis;if(!vis[z]){Q.push(z);vis[z]=1; } } } vis[v]=0;Q.pop(); } }

旅游景点atr