「AOJ1161～1170」の編集履歴（バックアップ）一覧に戻る

AOJ1161～1170 - (2013/01/24 (木) 15:29:18) のソース

*問い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);
     }
 }