Time Limit:5000MS Memory Limit:65536K
Total Submit:7 Accepted:5
Case Time Limit:1000MS
Description
给一张地图，地图上有一些城市，城市之间可能有线路连通，我们用一个无向图来表示以简化概念，每条边有个权值，表示选择这条边需要花费的费用。给定4对顶 点(可能重复)，求一个权值最小的边集，使得任意一对顶点可以由选出的边集中的边相连。
按照惯例，下面给出一个例子： 
Input
第1行2个整数，n和m，分别表示城市的个数和边的个数。
接下来n行，每行一个字符串，表示每个城市的名字。城市的名字为一个不超过20个字符，由小写字母构成的字符串。
再接下来m行，每行给出s1,s2和w，其中s1,s2为城市的名字，w为他们之间边的权值。
最后，给出4行，每行给出两个字符串，分别为要求的一对城市的名字。
Output
一行，输出最小的花费。
Sample Input
样例输入1：
10 15
stockholm
amsterdam
london
berlin
copenhagen
oslo
helsinki
dublin
reykjavik
brussels
oslo stockholm 415
stockholm helsinki 396
oslo london 1153
oslo copenhagen 485
stockholm copenhagen 522
copenhagen berlin 354
copenhagen amsterdam 622
helsinki berlin 1107
london amsterdam 356
berlin amsterdam 575
london dublin 463
reykjavik dublin 1498
reykjavik oslo 1748
london brussels 318
brussels amsterdam 173
stockholm amsterdam
oslo london
reykjavik dublin
brussels helsinki
样例输入2：
2 1
first
second
first second 10
first first
first first
second first
first first
Sample Output
样例输出1：
3907
样例输出2：
10
数据范围：
n<=30,m<=1000,w<=10000。
Source
这个题目非常好啊。。
以前WC有道题目跟这个很类似。。
首先答案肯定是个森另
所以状态可以看成Dp[at][mask]
at表示当前树的根在哪里，mask表示到过的地方（最多8位）
然后开始转移，跟那个不同的是，
如果mask里面状态是两两配对的话，
那么转移的时候经过的边权可以忽略。。
那么有2种转移。一种是at->go另一个地方。。
另一个是把同样在at的一个状态合并进来。。
然后瞎搞一下就OK了:
Code:
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#define rep(i,n) for(int i=0;i<n;i++)
const int inf=~0U>>1,maxn=30,maxc=8;
using namespace std;
map<string,int> Map;
vector<int> Mark[maxn];
int n,m,Ans=inf;
int E[maxn][maxn];
struct State
{
int at,mask;
State(){}
State(int _at,int _mask):
at(_at),mask(_mask){}
void mark(int go)
{
rep(i,Mark.size())
mask|=1<<(Mark[i]);
}
bool full()
{
return mask+1==(1<<8);
}
bool movefree()
{
rep(i,4)
{
int t=(mask>>(i*2))&3;
if(t!=0&&t!=3)return false;
}
return true;
}
int hash()const{return (at<<8)+mask;}
};
queue<State> Q;
int TDist[maxn<<8];
bool TinQ[maxn<<8];
int&Dist(const State&st){return TDist[st.hash()];}
bool&inQ(const State&st){return TinQ[st.hash()];}
void spfa()
{
memset(TDist,-1,sizeof TDist);
memset(TinQ,0,sizeof TinQ);
rep(at,n)
{
State now(at,0);
now.mark(at);
Dist(now)=0;inQ(now)=true;
Q.push(now);
}
while(Q.size())
{
State now=Q.front();Q.pop();
int c=Dist(now);inQ(now)=false;
if(now.full())
{
if(c<Ans)Ans=c;
continue;
}
bool free=now.movefree();
State next;int w;
//let’s go
rep(go,n)
if((w=E[now.at])!=inf)
{
if(free)w=0;
int nc=c+w;
next.at=go;next.mask=now.mask;
next.mark(go);
if(Dist(next)==-1||Dist(next)>nc)
{
Dist(next)=nc;
if(!inQ(next))
Q.push(next),inQ(next)=true;
}
}
//or we merge somthing
rep(j,(1<<8))
{
State tmp(now.at,j);
int tmpc=Dist(tmp);
if(tmpc!=-1)
{
State next(now.at,j|(now.mask));
int nc=tmpc+c;
if(Dist(next)==-1||Dist(next)>nc)
{
Dist(next)=nc;
if(!inQ(next))
Q.push(next),inQ(next)=true;
}
}
}
}
}
void init()
{
cin>>n>>m;string a,b;int c;
rep(i,n)rep(j,n)E[i][j]=inf;
rep(i,n)cin>>a,Map[a]=i;
rep(i,m)
{
cin>>a>>b>>c;
int s=Map[a],t=Map[b];
E[s][t]=E[t][s]=min(E[s][t],c);
}
memset(Mark,-1,sizeof Mark);
rep(i,8)
{
cin>>a;Mark[Map[a]].push_back(i);
}
}
int main()
{
//freopen("in","r",stdin);
//freopen("out","w",stdout);
init();
spfa();
cout<<Ans<<endl;
}
