AOJ 1138 Traveling by Stagecoach

解法

拡張ダイクストラを使ってd[現在のノード][使用した切符]を埋めていく。
使用した切符の枚数nはなのでbitで管理すればよい。
Queueには<距離,現在のノード,使用した切符>を入れ距離でソートして取り出せばよい。
計算量は多分くらいだと思う(違ったら指摘してください)...

ソースコード

void solve(int n,int m,int p,int a,int b){
    vi t(n);
    rep(i,n) cin>>t[i];
    vector<vector<int>> g(m,vi(m,INF));
    rep(i,p){
        int x,y,z;cin>>x>>y>>z;
        x--;
        y--;
        g[x][y]=z;
        g[y][x]=z;
    }
    sort(all(t));
    vector<vector<double>> d(m,vector<double>(1<<n,DINF));
    using P = pair<double,pair<int,int>>;                    // <distance , <node,used>>
    priority_queue<P,vector<P>,greater<P>> que;
    que.push(P(0,pii(a,0)));
    d[a][0] = 0;
    while(!que.empty()){
        auto p = que.top();que.pop();
        double dist = p.first;
        int v=p.second.first;
        int kip=p.second.second;

        if(dist>d[v][kip]) continue;

        for(int i=0;i<n;i++){       //i番目の切符を使用
            if((kip>>i)&1) continue;
            int nkip = (kip | (1<<i));
            for(int j=0;j<m;j++){
                if(g[v][j]==INF) continue;
                double cost=dist+(g[v][j]/(double)t[i]);
                if(cost<d[j][nkip]){
                    d[j][nkip] = cost;
                    que.push(P(cost,pii(j,nkip)));
                }
            }
        }
    }

    double ans = DINF;
    rep(i,(1<<n)){
        ans = min(ans,d[b][i]);
    }
    if(abs(DINF-ans)<0.00001) cout << "Impossible" << endl;
    else printf("%.20lf\n",ans);
}

int main(){
    int n,m,p,a,b;
    while(cin>>n>>m>>p>>a>>b){
        if(n==0 and m==0 and p==0 and a==0 and b==0) break;
        a--;
        b--;
        solve(n,m,p,a,b);
    }
}

感想

この問題自分で解けなかった...このくらいなら解けると思ったんだけど辺に対してどの切符を使えばいいかわからなかった...
これくらいは解けるようになりたい