1175: A Tour Around Hangzhou Submit Page Summary Time Limit: 2 Sec Memory Limit: 128 Mb Submitted: 111 Solved: 30 Description swimming来到杭州旅行,杭州是个美丽的城市,有很多美丽的景点.但让他头痛的是这些景点之间都有很长的距离,swimming决定选择便宜快捷的公交作为交通工具.杭州的公交网也十分复杂,不同的景点之间要转很多次公交才能到达,已知这些公交都只能站点上下车,并且相同的两个站点之间可能会有多班公交车.swimming想让你帮他设计一条旅游线路,花最少的钱旅游完所有的景点,最后回到出发地.
Input 输入有多组案例.
对于每个案例,第一行包含3个数据,公交站点的个数n(1<=n<=10^4),公交线路数量m(1<=m<=10^5),景点数量k(k<15);接下来m行每行包括三个数据si,ei,vi(0<=si,ei<n 1<=vi<=100)表示有一班往返于站点si和ei之间的交通线路费用为vi;接下来一行包括k个小于n的整数,表示这些站点附近有景点,swimming必须到达这些站点;最后一行包含一个小于n的整数,表示swimming的出发地.Output 如果swimming能旅游完所有的景点并且最后回到出发地,输出swimming坐公交旅行的最低花费;如果不能,输出”What a pity”(不加引号).对于每个案例,输出占一行.
Sample Input 5 6 2 0 1 3 1 2 2 0 2 1 2 3 2 1 3 3 3 4 4 1 3 0 Sample Output 9 Hint Source CSU_BMW正式组队纪念赛
最多只会用到 15 个点，先求出最短路， 然后更新当前状态下以其中一个为结尾的最优解
AC代码：
#include<cstdio> #include<map> #include<queue> #include<vector> #include<algorithm> using namespace std; const int INF = 0x3f3f3f3f / 2; const int K = 1e5 + 10; int n,m,k; struct node{ int a,vl; }; vector <node> v[K]; typedef pair<int,int> p; int b[15],mp[15][15],dis[K]; priority_queue <p,vector<p>,greater<p> > q; int dj(int s,int e){ fill(dis,dis + K,INF); dis[s] = 0; q.push(p(0,s)); while(!q.empty()){ p u = q.top(); q.pop(); int uf = u.first,us = u.second; if(uf > dis[us]) continue; for(int i = 0; i < v[us].size(); i++){ node w = v[us][i]; int d = w.vl + uf; if(d < dis[w.a]){ dis[w.a] = d; q.push(p(d,w.a)); } } } return dis[e]; } int dp[1 << 15][15]; void sc(){ for(int s = 0; s < 1 << k; s++) fill(dp[s],dp[s] + k,INF); dp[(1 << k ) - 1][0] = 0; for(int s = (1 << k) - 2; s >= 0; s--) for(int i = 0; i < k; i++) for(int j = 0; j < k ;j++) if(!(s >> j & 1)) dp[s][i] = min(dp[s][i],dp[s | 1 << j][j] + mp[i][j]); if(dp[0][0] == INF) printf("What a pity\n"); else printf("%d\n",dp[0][0]); } int main() { int x,y,fl; while(scanf("%d %d %d",&n,&m,&k) != EOF){ for(int i = 0; i <= n; i++) v[i].clear(); while(m--){ scanf("%d %d %d",&x,&y,&fl); v[x].push_back(node{y,fl}); v[y].push_back(node{x,fl}); } for(int i = 0; i < k ; i++) scanf("%d",&b[i]); scanf("%d",&fl); int ok = 0; for(int i = 0; i < k; i++) if(fl == b[i]) ok = 1,swap(b[i],b[0]); if(!ok) b[k++] = b[0],b[0] = fl; for(int i = 0; i < k ; i++){ for(int j = 0; j < i; j++) mp[i][j] = mp[j][i] = dj(b[i],b[j]); mp[i][i] = 0; } sc(); } return 0; }