ICPC Archive

残っている馬券と場所でdijkstra

#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
#define MAXN (10+1)
#define MAXM (30+1)
#define DM (1024+1) // 2^10 + 1
#define INF (1<<20)
int N,M,P,A,B;
int T[MAXN];
int F[MAXM][MAXM];
double D[MAXM][DM];
bool visited[MAXM][DM];

class State {
public:
  int p,use; // point, use, cost
  double c;
  State(int p,int use,double c) : p(p),use(use),c(c) {}
  bool operator < (const State &s) const {
    return c > s.c;
  }
};

double solve(int all) {
  memset(visited,0,sizeof(visited));
  for(int i=1;i<=M;i++) {
    for(int j=0;j<DM;j++) {
      visited[i][j] = false;
      D[i][j] = INF;
    }
  }
  priority_queue<State> PQ;
  PQ.push(State(A,0,0));
  D[A][0] = 0;
  while(!PQ.empty()) {
    State u = PQ.top(); PQ.pop();
    int p = u.p; int use=u.use;
    double c = u.c;
    if(p == B) {
      return D[p][use];
    }
    if(visited[p][use]) continue;
    if((use & all) == all) continue; // have no ticket
    visited[p][use] = true;

    for(int i=1;i<=M;i++) { // pos
      if(i==p) continue;
      if(F[p][i] >= INF) continue;
      for(int j=1;j<=N;j++) { // ticket
	int use2;
	if((use2=(use|(1<<j))) == use) continue;
	double cost = D[p][use] + (double)F[p][i]/T[j];
	if(cost < D[i][use2]) {
	  D[i][use2] = cost;
	  //printf("cost=%lf\n",cost);
	  PQ.push(State(i,use2,cost));
	}
      }
    }   

  }
  return -1;
}

main() {
  while(cin>>N>>M>>P>>A>>B,N) {
    for(int i=0;i<MAXM;i++) {
      for(int j=0;j<MAXM;j++) {
	F[i][j] = INF;
      }
    }
    for(int i=1;i<=N;i++) cin>>T[i];
    for(int i=1;i<=P;i++) {
      int x,y,z; cin>>x>>y>>z;
      F[x][y]=F[y][x] = z;
    }
    //puts("calc all...");
    int all=0;
    for(int i=0;i<N;i++) all = (all<<1) + 1;
    all <<= 1; // 1-origin
    //printf("solving...\n");
    double ans = solve(all);
    if(ans==-1) puts("Impossible");
    else cout << ans << endl;
  }
}