※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

問い1162 Discrete Speed

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1162
摩擦のない国でスタートの都市からゴールの都市まで到達する最短時間を答える問題。

解法
前にいた都市、今いる都市、今のスピードの3つの状態であらわされる点と、スピードを+1~-1まで加速して次の都市へ行く行為を線とみなして、グラフの問題として見ました。
とりえあずダイクストラ法でといてみましたがメモリ使用量は多いし、速度は出てないしであまりうまい解法でなかったようです。
賢い解法は貪欲法かもしれません。


#include<stdio.h>
#include<queue>
#include<string.h>
 
struct Car{
    double time,speed;
    int oldCity,nowCity;
    bool operator<(const Car& c)const{
        return time>c.time;
    }
};
 
void calc(int n,int m){
    int s,g;
  
    scanf("%d %d",&s,&g);
  
    double timeMemo[31][31][31];//timeMemo[前の都市][今の都市][速度]=最速到達時間
    double cityLen[31][31];
    int maxSpeed[31][31];
     
    memset(timeMemo,0,sizeof(timeMemo));
    memset(maxSpeed,0,sizeof(maxSpeed));
    memset(cityLen,0,sizeof(cityLen));
    int x,y,c;
    double d;
    for(int i=0;i<m;i++){
        scanf("%d %d %lf %d",&x,&y,&d,&c);
        maxSpeed[x][y]=maxSpeed[y][x]=c;
        cityLen[x][y]=cityLen[y][x]=d;
    }
     
    Car car,nextCar;
    car.oldCity=0;
    car.time=0;
    car.nowCity=s;
    car.speed=0;
    std::priority_queue<Car> qu;
    qu.push(car);
    double ans=-1;
    while(qu.empty()==false){
        car=qu.top();
        qu.pop();
        double t=timeMemo[car.oldCity][car.nowCity][(int)car.speed]; 
        if(t!=0&&t<=car.time)continue;
        timeMemo[car.oldCity][car.nowCity][(int)car.speed]=car.time;
        if(car.nowCity==g&&car.speed==1){
            if(ans==-1||ans>car.time)ans=car.time;
            break;
        }
        nextCar.oldCity=car.nowCity;
        for(int i=1;i<=n;i++){
            if(i==car.oldCity)continue;
            if(cityLen[car.nowCity][i]>0){
                nextCar.nowCity=i;
                for(int j=-1;j<=1;j++){
                    nextCar.speed=car.speed+j;
                    if(nextCar.speed<=0||maxSpeed[car.nowCity][i]<nextCar.speed)continue;
                     nextCar.time=car.time+cityLen[car.nowCity][i]/nextCar.speed;
                    if(ans!=-1&&ans<=nextCar.time)continue;
                    qu.push(nextCar);
                }
            }
        }
    }
   if(ans==-1){
        printf("unreachable\n");
    }else{
        printf("%.5lf\n",ans);
     }
}
 
  
int main(){
    int n,m;
     while(1){
        scanf("%d %d",&n,&m);
        if(n==0&&m==0)break;
        calc(n,m);
    }
}