ICPC 離散的速度 AOJ1162

多少工夫してみたがMLEが取れないため保留
問題自体は解けたため次に進む

#include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
  
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<double, int, int, int> T;
  
const ll MOD=1e9+7;
//const ll INF=1e18;
 
const double INF = 1000000.0;
  
int dx[]={0, 1, 0, -1};
int dy[]={-1, 0, 1, 0};
 
struct edge{ int to,d,c;};
 
 
 
int n,m,s,g;
double d[35][35][35];
double mind;
 
int main(){
    while(true){
        cin >> n >> m;
        if(n + m == 0) break;
        cin >> s >> g;
        mind = INF;
        vector<edge> G[35];
        for(int i = 0;i < m;i++){
            int a1,a2,a3,a4;
            cin >> a1 >> a2 >> a3 >> a4;
            edge tmp1 = {a2,a3,a4};
            G[a1].push_back(tmp1);
            edge tmp2 = {a1,a3,a4};
            G[a2].push_back(tmp2);
        }
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                for(int k = 0;k <= 31;k++){
                    d[i][j][k] = INF;
                }
            }
        }
		priority_queue<T,vector<T>,greater<T> > que2;
        for(int i = 0;i < G[s].size();i++){
            edge e = G[s][i];
            d[s][e.to][1] = (double) e.d;
            que2.push(make_tuple((double)e.d,1,s,e.to));
        }
        while(!que2.empty()){
            T t = que2.top(); que2.pop();
            double a1 = get<0>(t);
            int a2 = get<1>(t),a3 = get<2>(t),a4 = get<3>(t);
            if(d[a3][a4][a2] < a1 || a1 > mind)continue;
            for(int i = 0;i < G[a4].size();i++){
                edge e = G[a4][i];
                if(e.to == a3) continue;
                double tmp = (double) a1 + (double)e.d;
                if(d[a4][e.to][1] < tmp)continue;
                d[a4][e.to][1] =  tmp;
                if(mind < tmp) continue;
                if(e.to == g && mind > tmp)mind = tmp;
                que2.push(make_tuple(tmp,1,a4,e.to));
            }
        }
        if(mind == INF){
            cout << "unreachable" << endl;
            continue;
        }
        //queue<T> que;
        //priority_queue<T,vector<T>,greater<T> > que;
		priority_queue<T> que;
        for(int i = 0;i < G[s].size();i++){
            edge e = G[s][i];
            d[s][e.to][1] = (double) e.d;
            que.push(make_tuple((double)e.d,1,s,e.to));
        }
        while(!que.empty()){
            //T t = que.front(); que.pop();
            T t = que.top(); que.pop();
            double a1 = get<0>(t);
            int a2 = get<1>(t),a3 = get<2>(t),a4 = get<3>(t);
            if(d[a3][a4][a2] < a1 || a1 > mind)continue;
            for(int i = 0;i < G[a4].size();i++){
                edge e = G[a4][i];
                if(e.to == a3) continue;
                for(int j = -1;j <= 1;j++){
                    int v = a2 + j;
                    double tmp = (double)( a1 + (double)e.d / (double)v);
            //      if(a4 == 5 && e.to == 6 && v == 1) cout << "tmp" << tmp << ",a1" << a1 <<endl;
                    if(v <= 0 || v > e.c || d[a4][e.to][v] < tmp ||tmp > mind) continue;
                    d[a4][e.to][v] =  tmp;
                    if(e.to == g && v == 1 && mind > tmp)mind = tmp;
                    que.push(make_tuple(tmp,v,a4,e.to));
                }
            }
         
         
        }
    //  cout << "ans" << d[4][5][2] << endl;
 
 
 
        double ans = INF;
        for(int i = 1;i <= n;i++){
            double tmp = d[i][g][1];
            if(ans > tmp) ans = tmp;
        //  ans = min(ans,d[i][g][1]);
        }
        if(ans == INF){
            cout << "unreachable" << endl;
        }else{
        //  cout << ans << endl;
            printf("%lf\n",ans);
        }
    }
}

#include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
  
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<double, int, int, int> T;
  
const ll MOD=1e9+7;
//const ll INF=1e18;
 
const double INF = 1000000.0;
  
int dx[]={0, 1, 0, -1};
int dy[]={-1, 0, 1, 0};
 
struct edge{ int to,d,c;};
 
 
 
int n,m,s,g;
double d[35][35][35];
double mind;
 
int main(){
    while(true){
        cin >> n >> m;
        if(n + m == 0) break;
        cin >> s >> g;
        mind = INF;
        vector<edge> G[35];
        for(int i = 0;i < m;i++){
            int a1,a2,a3,a4;
            cin >> a1 >> a2 >> a3 >> a4;
            edge tmp1 = {a2,a3,a4};
            G[a1].push_back(tmp1);
            edge tmp2 = {a1,a3,a4};
            G[a2].push_back(tmp2);
        }
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                for(int k = 0;k <= 31;k++){
                    d[i][j][k] = INF;
                }
            }
        }
        //queue<T> que;
        priority_queue<T,vector<T>,greater<T> > que;
        for(int i = 0;i < G[s].size();i++){
            edge e = G[s][i];
            d[s][e.to][1] = (double) e.d;
            que.push(make_tuple((double)e.d,1,s,e.to));
        }
        while(!que.empty()){
            //T t = que.front(); que.pop();
            T t = que.top(); que.pop();
            double a1 = get<0>(t);
            int a2 = get<1>(t),a3 = get<2>(t),a4 = get<3>(t);
            if(d[a3][a4][a2] < a1 || a1 > mind)continue;
            for(int i = 0;i < G[a4].size();i++){
                edge e = G[a4][i];
                if(e.to == a3) continue;
                for(int j = -1;j <= 1;j++){
                    int v = a2 + j;
                    double tmp = (double)( a1 + (double)e.d / (double)v);
            //      if(a4 == 5 && e.to == 6 && v == 1) cout << "tmp" << tmp << ",a1" << a1 <<endl;
                    if(v <= 0 || v > e.c || d[a4][e.to][v] < tmp ||tmp > mind) continue;
                    d[a4][e.to][v] =  tmp;
                    if(e.to == g && v == 1 && mind > tmp)mind = tmp;
                    que.push(make_tuple(tmp,v,a4,e.to));
                }
            }
         
         
        }
    //  cout << "ans" << d[4][5][2] << endl;
 
 
 
        double ans = INF;
        for(int i = 1;i <= n;i++){
            double tmp = d[i][g][1];
            if(ans > tmp) ans = tmp;
        //  ans = min(ans,d[i][g][1]);
        }
        if(ans == INF){
            cout << "unreachable" << endl;
        }else{
        //  cout << ans << endl;
            printf("%lf",ans);
        }
    }
}