AOJ1138

Traveling by Stagecoach

■問題
m個の街がp本の道路でつながれている。
道路を利用するには券が必要で、移動にかかる時間は距離/券の数字だけの時間が掛かる。
また、券は１枚につき１回しか使えません。
あなたはn枚の券を持っていて街aから街bに行きたい時の最短時間を求めなさい。
またいけない場合は"Impossible"を出力しなさい。

■解法
今どの券を使ったかをbitで管理し、d[使用した県の情報][街の番号]でDPっぽいDijkstraする。

■ソース

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define F first
#define S second
using namespace std;

struct edge{
  int to,cost;
  edge(int to,int cost):to(to),cost(cost){}
};

typedef pair<double,pair<int,int> > P;

int n;
int m,p,a,b;
double t[11];
vector<edge> v[33];
double d[1<<9][33];

int main(void){
  while(1){
    cin >> n >> m >> p >> a >> b; if(!n) break;
    a--;b--;
    for(int i = 0; i < n; i++) cin >> t[i];
    for(int i = 0; i < 33; i++) v[i].clear();
    for(int i = 0; i < p; i++){
      int x,y,z;
      cin >> x >> y >> z;
      x--;y--;
      v[x].push_back(edge(y,z));
      v[y].push_back(edge(x,z));
    }

    priority_queue<P,vector<P>,greater<P> > que;
    for(int i = 0; i < 1<<9; i++) fill(d[i],d[i] + 33,1 << 28);
    d[0][a] = 0;
    que.push(P(0,make_pair(0,a)));
    while(!que.empty()){
      P p = que.top();que.pop();
      if(d[p.S.F][p.S.S] < p.F) continue;
      for(int i = 0; i < (int)v[p.S.S].size(); i++){
	for(int j = 0; j < n; j++){
	  if(p.S.F & 1 << j)continue;
	  if(d[p.S.F | 1 << j][v[p.S.S][i].to] > p.F + v[p.S.S][i].cost / t[j]){
	    d[p.S.F | 1 << j][v[p.S.S][i].to] = p.F + v[p.S.S][i].cost / t[j];
	    que.push(P(d[p.S.F | 1 << j][v[p.S.S][i].to],make_pair(p.S.F | 1 << j,v[p.S.S][i].to)));
	  }
	}
      }
    }
    double ret = (double)(1 << 28);
    for(int i = 0; i < 1 << 9; i++){
      ret = min(ret,d[i][b]);
    }
    if(ret == 1 << 28) puts("Impossible");
    else cout << ret << endl;
  }
}