题面

题目描述

给出一张有 (N) 个点 (M) 条边的加权有向无环图，接下来有 (Q) 个询问，每个询问包括 (2) 个节点 (X) 和 (Y) ，要求算出从 (X) 到 (Y) 的一条路径，使得密度最小（密度的定义为，路径上边的权值和除以边的数量）。

输入输出格式

输入格式：

第一行包括 (2) 个整数 (N) 和 (M) 。

以下 (M) 行，每行三个数字 (A) 、 (B) 、 (W) ，表示从 (A) 到 (B) 有一条权值为 (W) 的有向边。

再下一行有一个整数 (Q) 。

以下 (Q) 行，每行一个询问 (X) 和 (Y) ，如题意所诉。

输出格式：

对于每个询问输出一行，表示该询问的最小密度路径的密度（保留 (3) 位小数），如果不存在这么一条路径输出“OMG!”（不含引号）。

输入输出样例

输入样例：

输出样例：

5.000
5.500

说明

(1 leq N leq 50, 1 leq M leq 1000, 1 leq W leq 100000, 1 leq Q leq 100000)

思路

我们来做一点 (NOIP D1T2) 难度的图论题吧......来，洛谷 P4467。 --digger_sun

下午孙教练突然叫我们过去做了一些图论题，太毒瘤了 (qwq) 。特别是这道题，我没有做出来，因为完全没和动态规划联系到一起。最后则是 logeadd 的代码救了我。

进入正题。显然普通的松弛操作在这里不适用了，考虑使用记录状态的动态规划。定义 (dis[i][j][k]) 为从 (i) 点出发到达 (j) 点，中途恰好经过了 (k) 条边的最短距离。那么假设在从点 (s) 出发的一次最短路中，现在的状态是已经经过了 (k) 条边的点 (u) 和它的最短路径，对于一条边 ((u,v,d)) 我们就可以这样松弛：

[f[s][v][k+1]=min(f[s][v][k+1],f[u][v][k]+d) ]

最后统计答案时枚举经过的边数，就可以完成啦。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
int n,m,q,dis[55][55][1005];
int cnt,top[55],to[1005],len[1005],nex[1005];
int read()
{
    int re=0;
    char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) re=(re<<3)+(re<<1)+ch-'0',ch=getchar();
    return re;
}
void SPFA(int s)
{
    dis[s][s][0]=0;
    queue<PII>Q;
    Q.push(make_pair(s,0));
    while(!Q.empty())
    {
        int now=Q.front().first,edge=Q.front().second;Q.pop();
        for(int i=top[now];i;i=nex[i])
            if(dis[s][to[i]][edge+1]>dis[s][now][edge]+len[i])
            {
                dis[s][to[i]][edge+1]=dis[s][now][edge]+len[i];
                Q.push(make_pair(to[i],edge+1));
            }
    }
    return ;
}
int main()
{
    n=read(),m=read();
    memset(dis,0x3f,sizeof dis);
    for(int i=0;i<m;i++)
    {
        int x=read(),y=read(),z=read();
        to[++cnt]=y,len[cnt]=z,nex[cnt]=top[x],top[x]=cnt;
    }
    q=read();
    while(q--)
    {
        int s=read(),t=read();
        SPFA(s);
        double ans=INF;
        for(int i=1;i<=m;i++) if(dis[s][t][i]!=INF) ans=min(ans,double(dis[s][t][i])/double(i));
        if(ans!=INF) printf("%.3f
",ans);
        else puts("OMG!");
    }
    return 0;
}