4856 这题说的是给了一个图 这个图有很多的隧道每个隧道是单向的 只能从一个入口进入从另一个入口出来 要求计算出走完这些隧道花的总时间 因为这个图是一个网格行的然后 先用bfs算出隧道的出口到每个隧道的入口的最短距离然后进行一次TSP 意思是 dp[S][v] 表 示 从 点 v 出发已经经过了 S中每个二进制表示的点然后求得了结果
#include <iostream>
#include <string.h>
#include <cstdio>
#include <queue>
using namespace std;
typedef pair<int,int> F;
const int maxn =;
struct node{
int fx,fy,tx,ty;
}P[maxn];
int x[]={,,,-};
int y[]={,-,,};
char map[maxn][maxn];
int MT[maxn][maxn],N,M,dist[maxn][maxn];
int dp[<<][];
void bfs(int xx,int yy){
memset(MT,-,sizeof(MT));
queue<F> Q;
F a;
a.first =xx;
a.second=yy;
Q.push(a);
MT[xx][yy]=;
while(!Q.empty()){
F E=Q.front();
Q.pop();
for(int i =;i<; ++ i){
int xt=E.first+x[i];
int yt=E.second+y[i];
if( xt> && xt <= N && yt > && yt <= N && MT[xt][yt]==-&&map[xt][yt]=='.')
{
MT[xt][yt]= MT[E.first][E.second] + ;
a.first =xt;
a.second =yt;
Q.push(a);
}
}
}
}
void solve(){
for(int i = ; i<M ; ++i){
bfs( P[i].tx, P[i].ty);
for(int j = ; j<M ; ++ j)
if(i!=j)
dist[i][j]=MT[ P[j].fx ][ P[j].fy ];
else dist[i][j]=;
dist[i][]=dist[][i]=;
}
}
int main()
{
while(scanf("%d%d",&N,&M)==){
memset(dist,-,sizeof(dist));
for(int i =; i<= N; ++i){
getchar();
for(int j =; j<=N; ++j)
map[i][j] =getchar();
}
M++;
for(int i =; i<M ;++i)
scanf("%d%d%d%d",&P[i].fx,&P[i].fy,&P[i].tx,&P[i].ty);
solve();
for(int S =; S<(<<M); ++S)
fill(dp[S],dp[S]+M,);
dp[(<<M)-][]=;
for(int S=(<<M)- ; S>=; S--){
for(int v=; v<M; ++v)
for(int u=; u<M; ++u){
if((S&(<<u))==&&dist[u][v]!=-&& dp[S|<<u][u]!=){
dp[S][v] =min(dp[S][v],dp[S|<<u][u]+dist[u][v]);
}
}
}
if(dp[][]!=)
printf("%d\n",dp[][]);
else printf("-1\n");
}
return ;
}