JIsoo

首先考虑floyd本质就是dp，然后扔进新的一维$f_{i,j,k}$,表示i和j之间经过k条边的最短路

枚举的时候是5个for？那也太疯狂了。

考虑一下如果i和j经过k能够作为当前边数的最短路的话，如果k和i，j距离不是1，那么在这一条路径上，一定可以用距离i为1的那个点来更新，这样的话其实我们只需要枚举四维就可以了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define int long long
using namespace std;
template<class T>
void read(T &now){
    now=0;
    char c=getchar();
    int f=1;
    while((!isdigit(c))){
        if(c=='-') f=-1;
    //  cout<<isdigit(c)<<" "<<c<<" ";
        c=getchar();
    }
    while(isdigit(c)){
        now=(now<<1)+(now<<3)+c-'0';
        c=getchar();
    }
    now*=f;
}
int n,m;
int ma[60][60];
int f[60][60][1005];
int x,y,z;
signed main(){
    memset(f,0x3f,sizeof(f));
    read(n);read(m);
    for(int i=1;i<=m;i++){
        read(x);read(y);read(z);
        f[x][y][1]=min(f[x][y][1],z);
    } 
    for(int w=2;w<=m;++w){
        for(int k=1;k<=n;++k){
            for(int i=1;i<=n;++i){
                for(int j=1;j<=n;++j){
                    f[i][j][w]=min(f[i][j][w],f[i][k][w-1]+f[k][j][1]);
                }
            }
        }
    }
    double ans;
    read(z);
    for(int i=1;i<=z;++i){
        read(x);read(y);
        ans=9999999999999;
        for(int j=1;j<=m;++j){
        //  cout<<f[x][y][j]<<endl;
            if(f[x][y][j]!=f[0][0][0]){
                ans=min(ans,((double)((double)f[x][y][j]/(double)j)));
        //      cout<<ans<<endl;
            }
        }
        if(ans>=9999999999999){
            printf("OMG!n");
        }else{
            printf("%.3lfn",ans);
        }
    }
    return 0;
}