PKU 2686 Traveling by Stagecoach

• 拡張ダイクストラ法
• [最後に訪れた頂点][使用したチケットの集合]でダイクストラ
• 又は[最後に訪れた頂点][何枚目のチケット化]を外側でチケットの順番を回しても良い
• 以下の回答はPKUではTLE

struct State {
	double cost;
	int node;
	int nextTicket;
	State(double cost, int node, int nextTicket) : cost(cost), node(node), nextTicket(nextTicket) { }
	bool operator < (const State& rh) const {
		return cost != rh.cost ? cost > rh.cost :
			node != rh.node ? node < rh.node :
			nextTicket < rh.nextTicket;
	}
};

int main() {
	for (int n, m, p, a, b; cin >> n >> m >> p >> a >> b && (n || m || p || a || b); ) {
		vector<double> tickets;
		REP(i, n) {
			double ticket;
			cin >> ticket;
			tickets.push_back(ticket);
		}
		sort(ALL(tickets));

		// dst, cost
		vector<vector<pair<int, double> > > g(m + 1);
		REP(i, p) {
			int x, y;
			double z;
			cin >> x >> y >> z;
			g[x].push_back(make_pair(y, z));
			g[y].push_back(make_pair(x, z));
		}

		double answer = INT_MAX;
		do {
			double dp[32][16];
			fill_n((double*)dp, sizeof(dp) / sizeof(double), INT_MAX);
			dp[a][0] = 0;

			priority_queue<State> q;
			q.push(State(0, a, 0));

			while (!q.empty()) {
				const State current = q.top();
				q.pop();

				if (abs(dp[current.node][current.nextTicket] - current.cost) > EPS) {
					continue;
				}

				for (vector<pair<int, double> >::iterator it = g[current.node].begin(), itEnd = g[current.node].end(); it != itEnd; ++it) {
					const State next(current.cost + it->second / tickets[current.nextTicket], it->first, current.nextTicket + 1);
					if (next.nextTicket <= n && dp[next.node][next.nextTicket] > next.cost + EPS) {
						dp[next.node][next.nextTicket] = next.cost;
						q.push(next);
					}
				}
			}

			REP(i, n + 1) {
				answer = min(answer, dp[b][i]);
			}

		} while (next_permutation(ALL(tickets)));

		if (answer == INT_MAX) {
			printf("Impossible\n");
		} else {
			printf("%.03f\n", answer);
		}
	}
}