AOJ 0244 Hot Spring Trip

問題文

Hot Spring Trip

感想

明らかに前問より簡単。ダイクストラを用いた最短経路問題に慣れていたらやるだけに感じた。10分で書けた。これ10分ってタイピング速度向上してる感ある。

DPするにしても探索するにしても何にしてもそうだけど、状態に対する感覚の持ち方はかなり大切で、(今どこにいるか)ではなく、(今どんな状態か)を意識することがDPとかダイクストラ習得する上で大切だと思った。

解法

色々方法はあるだろうけど、僕は以下の方法で解きました。無向グラフであると仮定して解いた。

道路を移動する通常料金を通常コストとし、無料権を消費するのを特殊コストと呼ぶことにする。

• 与えられたグラフを通常コストをそのまま,特殊コスト0という設定で繋ぐ。
• 2回の移動(1回で行けても遠回りしたら2回で行ける組も含む)を列挙。
• それらを通常コスト0,特殊コスト1で繋ぐ。

今どこにいるか(100通り) 特殊なコストの残り数(2通り(0or1))の情報を頂点としたダイクストラ。

ソース

ワーシャルフロイドわざわざやってて頭悪い

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
struct NODE{
    int to,cost,ticket;
    NODE(int to,int cost,int ticket) : to(to) , cost(cost) , ticket(ticket) {};
    NODE(){}
};
bool operator < (const NODE &a,const NODE &b){
    return a.cost > b.cost;
}
 
int main(){
    int n,m;
    while(cin >> n >> m && n){
        vector< vector<NODE> > g(n);
        int wf[2][100][100]={};
        for(int i = 0 ; i < 2 ; i++)
            for(int j = 0 ; j < 100 ; j++)
                for(int k = 0 ; k < 100 ; k++)
                    wf[i][j][k] = 0;
 
        for(int i = 0 ; i < m ; i++){
            int a,b,c;
            cin >> a >> b >> c;
            a--,b--;
            g[a].push_back(NODE(b,c,0));
            g[b].push_back(NODE(a,c,0));
            wf[0][a][b] = wf[0][b][a] = 1;
        }
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < n ; j++){
                for(int k = 0 ; k < n ; k++){
                    wf[1][j][k] |= wf[0][j][i] & wf[0][i][k]; 
                }
            }
        }
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < n ; j++){
                if(wf[1][i][j]){
                    g[i].push_back(NODE(j,0,1));
                     
                }
            }
        }
         
        priority_queue<NODE> Q;
        Q.push(NODE(0,0,1));
        int done[100][2] = {};
        while(Q.size()){
            NODE q = Q.top(); Q.pop();
            if( done[q.to][q.ticket]++ ) continue;
            if( q.to == n - 1 ){
                cout << q.cost << endl;
                break;
            }
            for(int i = 0 ; i < g[q.to].size() ; i++)
                if( q.ticket - g[q.to][i].ticket >= 0 )
                    Q.push(NODE(g[q.to][i].to,q.cost+g[q.to][i].cost,q.ticket - g[q.to][i].ticket));
             
        }
         
         
    }
}