2686 Traveling by Stagecoach

問題概要

AOJに日本語の問題文があるのでそちら参照。
（http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1138&lang=jp）

解法

AOJは拡張ダイクストラで通るがPKUだとTLEだった。
ビットDPの解法だと通った。
なんでこっちのほうが速いんだろ……グラフが密でlog nがかえって重くなっている感じだろうか。

ソースコード

int n,m,p,s,t,l[8];
vector<vector<pi> >e;
double dp[30][1<<8];

int main()
{
	while(scanf("%d%d%d%d%d",&p,&n,&m,&s,&t),s)
	{
		s--; t--; e.clear(); e.resize(n);
		rep(i,p)scanf("%d",l+i);
		rep(i,m)
		{
			int a,b,c; scanf("%d%d%d",&a,&b,&c); a--; b--;
			e[a].pb(mp(b,c)); e[b].pb(mp(a,c));
		}
		rep(i,n)rep(j,1<<p)dp[i][j]=1e9;
		dp[s][(1<<p)-1]=0;
		
		for(int i=(1<<p)-1;i>0;i--)rep(j,n)
		{
			fr(k,e[j])rep(ii,p)if(i&1<<ii)
			dp[k->first][i^1<<ii]=min(dp[k->first][i^1<<ii],dp[j][i]+k->second*1.0/l[ii]);
		}
		double ans=1e9; rep(i,1<<p)ans=min(ans,dp[t][i]);
		if(ans==1e9)puts("Impossible"); else printf("%f\n",ans);
	}
	return 0;
}