點擊打開鏈接

題意：

游戲園里有N個區域，有M條邊連接這N個區域，有K個要訪問的景點。對于每個景點告訴你這個景點所在的區域，要訪問這個景點需要等待一定時間，如果沒有FastPass，等待時間有Ti，否則等待時間為FTi，接下來的Ni，表示有Ni個區域可以得到這個景點的FastPass，問從區域1出發，再回到區域1所需要的最少時間。

思路：

狀態壓縮，dis[i][s1][s2]，表示當前走到這個點，s1表示拿到了哪些景點的FastPass，s2表示已經訪問了哪幾個景點。

但是需要注意的是：當游覽過某個景點之后，就認為拿著了這個景點的票了！??！這個優化很重要

代碼：

#include <bits/stdc++.h>using namespace std;int n,m,k;int dis[55][55],dp[55][1<<8][1<<8],pos[10],t[10],ft[10],pas[55];int ans;void init(){	ans = 0x3f3f3f3f;	memset(dp,0x3f,sizeof(dp));	memset(dis,0x3f,sizeof(dis));	memset(pas,0,sizeof(pas));}void floyd(){	for(int k=1; k<=n; k++)		for(int i=1; i<=n; i++)			for(int j=1; j<=n; j++)				dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);}void solve(){	dp[1][0][0] = 0;	for(int s1=0; s1<(1<<k); s1++){		for(int s2=0; s2<(1<<k); s2++){			for(int i=1; i<=n; i++){				int now = dp[i][s1][s2];				if(now==0x3f3f3f3f) continue;				if(s2==(1<<k)-1) ans = min(ans,now+dis[i][1]);				for(int j=0; j<k; j++){					if((s2&(1<<j)) == 0){ // 沒走過第j個景點						int& nxt = dp[pos[j]][s1|pas[pos[j]]][s2^(1<<j)]; // 當游覽過某個景點之后，就認為拿著了這個景點的票了?。?！						int add = dis[i][pos[j]];						if(s1 & (1<<j)) add += ft[j];						else add += t[j];						nxt = min(nxt,now+add);					}				}				for(int j=1; j<=n; j++){  // 中轉 通過j得到fastpass					int& nxt = dp[j][s1|pas[j]][s2];					int add = dis[i][j];					nxt = min(nxt,now+add);				}			}		}	}}int main(){	int T; cin>>T;	for(int cas=1; cas<=T; cas++){				init();		cin >> n >> m >> k;		for(int i=1; i<=m; i++){			int u,v,w; cin>>u>>v>>w;			dis[u][v] = w; dis[v][u] = w;		}		for(int i=0;i<n;i++) dis[i][i]=0; 		floyd();		for(int i=0; i<k; i++){			cin >> pos[i] >> t[i] >> ft[i];			int num; cin>>num;			for(int j=0; j<num; j++){				int tmp; cin>>tmp;				pas[tmp] |= (1<<i);			}		}		solve();		cout << "Case #" << cas << ": " << ans << endl;	}}