ICPC 2005年国内予選問題D

馬車券問題。ちょっと気になったので解きなおし。
基本的な方針はこれまでいろいろなところで議論されているものと同じだけど(DAG上最短路)
問題は生成されたグラフのトポロジカルソートをどうやって得るか。

以下の方法でうまくいくと昨日になってはじめて気づきました。

#include<iostream>
#include<vector>
using namespace std;
int main(){
  while(true){
    int n,m,p,a,b;
    cin>>n>>m>>p>>a>>b;
    if(!(n|m|p|a|b))break;
    a--,b--;
    vector<int> ts(n);
    for(int i=0;i<n;i++){
      cin>>ts[i];
    }
    vector<vector<int> > dest(m);
    vector<vector<int> > weight(m);
    for(int i=0;i<p;i++){
      int a,b,c;
      cin>>a>>b>>c;
      a--,b--;
      dest[a].push_back(b);
      weight[a].push_back(c);
      dest[b].push_back(a);
      weight[b].push_back(c);
    }
#define INF 1e10
    vector<vector<double> > ans(1<<n,vector<double>(m,INF));
    double opt = INF;
    ans[(1<<n)-1][a]=0.0;
    for(int i=(1<<n)-1;i>=0;--i){
      for(int j=0;j<m;j++){
	if(ans[i][j]==INF)continue;
	if(j==b)opt = min(opt, ans[i][j]);
	vector<int> &ds = dest[j];
	vector<int> &ws = weight[j];
	for(int k=0;k<(int)ds.size();k++){
	  for(int l=0;l<n;l++){
	    if(!(i&(1<<l)))continue;
	    ans[i&~(1<<l)][ds[k]] = min(ans[i&~(1<<l)][ds[k]], ans[i][j]+(double)ws[k]/ts[l]); 
	  }
	}
      }
    }
    if(opt==INF)cout<<"Impossible"<<endl;
    else cout << opt << endl;
  }
  return 0;
}

DPの最外周ループをこうしてしまってよいことに気づかなかった。
最初にPKUで通したコードとは雲泥の差が。