原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=4640
解题思路：
首先用一个简单的2^n*n的dp可以求出一个人访问一个给定状态的最小花费，因为这i个人是等价的，所以用dp[i][mask]表示i个人跑完mask这个状态的最小花费，所以首先枚举集合mask，对于dp[i][mask]，枚举mask的子集v，dp[i][mask]可以由dp[1][v],dp[i-1][mask^v]转移过来，注意这里用来合并的集合是不能有重复的，这个类似背包……这样就可以算出对于每个状态三个人访问完的最小花费，之后对于给定的需要访问的状态，枚举包含这个给定状态的集合更新答案就可以了……注意对于刚开始给定的图是不能floyd的，因为要求任意两个人的路径不能相交……还有就是1这个节点可以每个人经过多次，这里需要特殊处理一下……
以上摘自杭电的解题报告
下面是我还未写完的代码，我还不会做这个题，所以···还得想想····以后会改好的
#include <cstdio>
#include <queue>
using namespace std;
#define N (1<<17)+5
#define INF 100000000
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b int n,status; //人数，学妹位置的状态
int d[N][],dp1[N],dp2[N];
bool in[N][];
int edge[][];
queue<int> qu;
void initScan()
{
int m;
scanf("%d%d",&n,&m);
for(int i=; i<n; ++i)
{
for(int j=; j<n; ++j)
{
if(i == j) edge[i][j] = ;
else edge[i][j] = INF;
}
}
while(m--)
{
int u,v,c;
scanf("%d%d%d",&u,&v,&c);
--u,--v;
edge[u][v] = min(edge[u][v],c);
edge[v][u] = edge[u][v];
}
int k;
status = ;
scanf("%d",&k);
while(k--)
{
int sis;
scanf("%d",&sis);
status |= (<<(sis-));
}
status >>= ;
}
void bfs()
{
memset(in,,sizeof(in));
memset(d,0x3f,sizeof(d));
qu.push();//先城市
qu.push();//后状态
d[][] = ;
in[][] = true;
while(!qu.empty())
{
int i = qu.front();//状态
qu.pop();
int j = qu.front();//城市
qu.pop();
in[i][j] = false;
for(int k=; k<n; ++k)
{
int w = i |( << k);
if(d[w][k] > d[i][j] + edge[j][k] )
{
d[w][k] = d[i][j] + edge[j][k];
if(!d[w][k])
{
qu.push(k);
qu.push(w);
in[w][k] = ;
}
}
}
}
}
void DP1()
{
memset(dp1,0x3f,sizeof(dp1));
for(int i=; i<(<<n); ++i)
{
for(int j=; j<n; ++j)
dp1[i>>] = min(dp1[i>>],d[i][j]);
}
}
void DP2()
{
for(int i=; i<(<<n); ++i)
{
int j = i;
while(j)
{
j=(j-)&i;
dp2[i] = min( dp2[i],max(dp2[j],dp2[i^j]) );
}
}
}
int solve()
{
int ans = INF;
int j = status;
while(j)
{
j=(j-)&status;
ans = min( ans,max(dp2[j],dp1[status^j]) );
ans = min(ans,max(dp2[status^j],dp1[j]) );
}
return ans;
} int main()
{
freopen("in.cpp","r",stdin);
freopen("myout.cpp","w",stdout);
int t;
scanf("%d",&t);
for(int ser=; ser<=t; ++ser)
{
initScan();
bfs();
DP1();
for(int i=; i<(<<n); ++i)
printf("d[%d] = %d\n",i,dp1[i]);
DP2();
int ans = solve();
printf("Case %d: ",ser);
if(ans == INF) printf("-1\n");
else printf("%d\n",ans);
}
return ;
}
下面是标程1：
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f
#define N 101
int sta;
int d[N][N];
int dp[ << ][];
bool in[ << ][];
int dp_1[ << ], dp_2[ << ];
int main() {
int t, cas = ;
scanf(" %d", &t);
while (t--) {
int n, m;
scanf(" %d %d", &n, &m);
// if(cas==13) printf("%d %d\n",n,m);
memset(d, 0x3f, sizeof(d));
for (int i = ; i < m; i++) {
int x, y, s;
scanf(" %d %d %d", &x, &y, &s);
// if(cas==13) printf("%d %d %d\n",x,y,s);
d[x][y] = min(d[x][y], s);
d[y][x] = d[x][y];
} queue<int> qu;
qu.push();
qu.push();
memset(in, , sizeof(in));
memset(dp, 0x3f, sizeof(dp));
dp[][] = ;
in[][] = true; while (!qu.empty()) {
int s_sta = qu.front();
qu.pop();
int s = qu.front() + ;
qu.pop();
in[s_sta][s - ] = false; for (int i = ; i < n; i++) {
int to = i + ;
int t_sta = ( << i) | s_sta;
if (to == )
continue;
if (dp[t_sta][to - ] > dp[s_sta][s - ] + d[s][to]) {
dp[t_sta][to - ] = dp[s_sta][s - ] + d[s][to];
if (!in[t_sta][to - ]) {
in[t_sta][to - ] = ;
qu.push(t_sta);
qu.push(to - );
}
}
}
} memset(dp_1, 0x3f, sizeof(dp_1));
for (int i = ; i < ( << n); i++) {
for (int j = ; j < n; j++) {
dp_1[i >> ] = min(dp_1[i >> ], dp[i][j]);
}
} int tar = , k;
scanf(" %d", &k);
// if(cas==13) printf("%d\n",k);
while (k--) {
int x;
scanf(" %d", &x);
// if(cas==13) printf("%d ",x);
tar |= ( << (x - ));
}
int ans = INF;
int tol = ( << (n - )) - ;
memcpy(dp_2, dp_1, sizeof(dp_1));
for (int i = ; i < ( << (n - )); i++) {
for (int j = i; j; j = (j - ) & i) {
dp_2[i] = min(dp_2[i], max(dp_1[j], dp_1[i ^ j]));
}
}
for (int i = tol; i; i--) {
for (int j = i;; j = (j - ) & i) {
if ((i & tar) == tar) {
ans = min(ans, max(dp_1[j], dp_2[i ^ j]));
}
if (j == )
break;
}
}
if (ans == INF)
ans = -;
printf("Case %d: %d\n", cas++, ans);
}
return ;
}
标程2：
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
using namespace std;
typedef __int64 lld;
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define maxn 20
struct Edge
{
int v,s,next;
}edge[];
int head[maxn];
int pos;
void insert(int x,int y,int s)
{
edge[pos].v=y;
edge[pos].s=s;
edge[pos].next=head[x];
head[x]=pos++;
}
int dis[<<][];
bool vis[<<][];
pair<int,int>queue[];
int rear,front;
int maxQ=;
int dp[<<];
int f[<<];
int main()
{
// freopen("input.txt","r",stdin);
int cas;
scanf("%d",&cas);
for(int cc=;cc<=cas;cc++)
{
int n,m;
scanf("%d %d",&n,&m);
memset(head,,sizeof(head));
pos=;
while(m--)
{
int x,y,s;
scanf("%d %d %d",&x,&y,&s);
insert(x,y,s);
insert(y,x,s);
}
memset(dis,-,sizeof(dis));
memset(vis,false,sizeof(vis));
rear=front=;
for(int i=head[];i;i=edge[i].next)
{
int v=edge[i].v;
v-=;
if(dis[<<v][v] == - || edge[i].s < dis[<<v][v])
{
dis[<<v][v]=edge[i].s;
if(!vis[<<v][v])
{
vis[<<v][v]=true;
queue[front++]=mp(<<v,v);
}
}
}
while(rear != front)
{
int mask=queue[rear].X;
int u=queue[rear].Y;
rear++;
if(rear == maxQ)
rear=;
vis[mask][u]=false;
for(int i=head[u+];i;i=edge[i].next)
{
int v=edge[i].v;
if(v == )
continue;
v-=;
int next=mask|(<<v);
if(dis[next][v] == - || dis[mask][u]+edge[i].s < dis[next][v])
{
dis[next][v]=dis[mask][u]+edge[i].s;
if(!vis[next][v])
{
vis[next][v]=true;
queue[front++]=mp(next,v);
if(front == maxQ)
front=;
}
}
}
}
memset(dp,-,sizeof(dp));
dp[]=;
int T=<<(n-);
for(int mask=;mask<T;mask++)
for(int i=;i<n-;i++)
{
if(dis[mask][i] == -)
continue;
if(dp[mask] == - || dis[mask][i] < dp[mask])
dp[mask]=dis[mask][i];
}
for(int mask=;mask<T;mask++)
f[mask]=dp[mask];
for(int k=;k<;k++)
{
for(int u=T-;u>;u--)
for(int v1=u;;v1=(v1-)&u)
{
int v2=u^v1;
if(dp[v1] == - || f[v2] == -)
{
if(v1 == )
break;
continue;
}
if(dp[u] == - || max(dp[v1],f[v2]) < dp[u])
dp[u]=max(dp[v1],f[v2]);
if(v1 == )
break;
}
}
int Q;
scanf("%d",&Q);
int mask=;
while(Q--)
{
int x;
scanf("%d",&x);
x-=;
mask|=<<x;
}
int ans=-;
for(int u=;u<T;u++)
if((u&mask) == mask)
{
if(dp[u] == -)
continue;
if(ans == - || dp[u] < ans)
ans=dp[u];
}
printf("Case %d: %d\n",cc,ans);
}
return ;
}