我用dp的思路，但是我是djstra而不是floyd。 dp保存的是在k条边的情况下i到j最小密度。 洛谷我AC了，但是牛客只过了67不知道为什么。 牛客最后输出我尝试小数点后5位也不行，long double也试了，应该不是精度问题，而且我看没有题解是这种做法，希望大佬看看给我解答一下问题在哪里。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m;
#define N 1010
ll e[N],ne[N],h[N];
double w[N];
double dp[60][60][60];
ll idx=1;
#define pdl pair<double,pair<ll,ll>>
void add(ll a,ll b,double c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}

void solve(ll x)
{
    
    priority_queue<pdl,vector<pdl>,greater<pdl>> q;
    q.push({0,{0,x}});
    while(!q.empty())
    {
        auto [d,p]=q.top();
        auto [k,u]=p;
        q.pop();
        for(ll i=h[u];i;i=ne[i])
        {
            if(dp[x][e[i]][k+1]>(d+w[i])/(k+1))
            {
                dp[x][e[i]][k+1]=(d+w[i])/(k+1);
                q.push({d+w[i],{k+1,e[i]}});
            }
        }
    }
    
}

int main()
{
    cin>>n>>m;
    for(ll k=1;k<=55;k++)
    {    
        for(ll i=1;i<=55;i++)
        {
            for(ll j=0;j<=55;j++)
            {
                dp[k][i][j]=1e10;
            }
        }
    }
    for(ll i=1;i<=m;i++)
    {
        ll u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
    }
    for(ll i=1;i<=n;i++)
    solve(i);
    ll q;
    cin>>q;
    for(ll i=1;i<=q;i++)
    {
        ll a,b;
        cin>>a>>b;
        double ans=1e11;
        for(ll j=0;j<=55;j++)
        {
            ans=min(ans,dp[a][b][j]);
        }
        if(ans>1e9)cout<<"OMG!"<<endl;
        else printf("%.3lf\n",ans);
    }
    return 0;
}