状压dp第一题：很多东西没看懂，慢慢来，状压dp主要运用了位运算，二进制处理
集合｛0，1，2，3，....，n-1｝的子集可以用下面的方法编码成整数
像这样，一些集合运算就可以用如下的方法来操作：
1.空集....................0
2.只含有第i个元素的集合｛i｝................1 << i
3.含有全部n个元素的集合{0,1,2,3,....,n - 1}.............(1 << n) - 1
4.判断第i个元素是否属于集合S.................................if(S >> i & 1)
5.向集合中加入第i个元素S ∪ {i}...............................S | 1 << i
6.从集合中除去第i个元素S \ {i}..................................S & ~(1 << i)
7.集合S和T的并集S∪T...............................................S | T
8.集合S和T的交集S∩T................................................S & T
题意：一个人在m个城市的国家旅行，他有n张车票，这个国家有p条路，一条路连接两个城市，他要从a城市到b城市，从一个城市到另一个城市所需要的时间是路的长度除以车票的面值，面值表示可以有多少匹马来拉，求最短的时间。
题解：看代码，主要就是状压dp+dijkstra
还有一点就是min只能用于整形，这样的话要算float的话就只能用宏定义了
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<iomanip>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pi acos(-1)
#define ll long long
#define mod 10007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define MIN(a,b) a<b ? a:b using namespace std; const double g=10.0,eps=1e-;
const int N=,maxn=,inf=<<; int n,m,p,a,b,t[maxn];
int d[maxn][maxn];
double dp[<<N][maxn]; void solve()
{
for(int i=;i< <<n;i++)//从0到1<<n是所以子集
fill(dp[i],dp[i]+m,inf);//把dp初始化
dp[(<<n)-][a-]=;//起始点设为0，就是dijkstra算法
double res=inf;
for(int s=(<<n)-;s>=;s--)
{
res=MIN(res,dp[s][b-]);//记录答案
for(int v=;v<m;v++)//起点
for(int i=;i<n;i++)//这是车票
if(s>>i&)//判断第i个元素是否属于s
for(int u=;u<m;u++)//终点
if(d[v][u]>=)//使用车票i，从v到u
dp[s& ~(<<i)][u]=MIN(dp[s& ~(<<i)][u],dp[s][v]+(double)d[v][u]/t[i]);
}
if(res==inf)cout<<"Impossible"<<endl;
else cout<<res<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
cout<<setiosflags(ios::fixed)<<setprecision();
while(cin>>n>>m>>p>>a>>b){
if(!n&&!m)break;
for(int i=;i<n;i++)cin>>t[i];
memset(d,-,sizeof d);//距离初始化为-1
for(int i=;i<p;i++)
{
int x,y,z;
cin>>x>>y>>z;
x--;
y--;
d[x][y]=d[y][x]=z;//保存距离信息，这是无向无环图
}
solve();
}
return ;
}