DP，每次扫描一行然后更新DP[i] = k; i表示B，k表示对应的最少价格，最后，扫描最后一行里边所有的可能性，取出最大值

#include <iostream>
#include<string>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<vector>
using namespace std;
struct ca
{
    double b, v;
}  con[110][110];
int dp[2000], dic[2000];
int main()
{
    freopen("D:\\CPPProgram\\ACM\\in.txt", "r", stdin);
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int test_num;
        memset(con, 0.0, sizeof con);
        memset(dic, 0, sizeof dic);
        //memset(dp, 0, sizeof dp);
        for(int m=0; m<1999; m++) dp[m] = 200000;
        scanf("%d", &test_num);
        for (int i=0; i<test_num; i++)
        {
            int pair_num;
            scanf("%d", &pair_num);
            for(int j=0; j<pair_num; j++)
            {
                scanf("%lf %lf", &con[i][j].b, &con[i][j].v);
            }
        }
        for(int i=0; ; i++)
        {
            if(con[0][i].b == 0) break;
            dic[(int)con[0][i].b] = 1;
        }
        for(int i=0; ; i++)
        {
            if(con[0][i].b == 0) break;
            dp[(int)con[0][i].b] = min((int)con[0][i].v, dp[(int)con[0][i].b]);
        }
        for(int i=1; ; i++)
        {
            int dic_mid[2000], dp_mid[2000];
            memset(dic_mid, 0, sizeof dic_mid);
            //memset(dp_mid, 101, sizeof dp_mid);
            for(int m=0; m<1999; m++) dp_mid[m] = 200000;
            if(con[i][0].b == 0) break;
            for(int j=0; ; j++)
            {
                if(con[i][j].b == 0) break;
                double Max = -1.0;
                for(int m=0; m<1999; m++)
                {
                    if(dic[m] == 0) continue;
                    else
                    {
                        double bb = min((int)con[i][j].b, m);
                        dic_mid[(int)bb] = 1;
                        dp_mid[(int)bb] = min(dp_mid[(int)bb], dp[m]+(int)con[i][j].v);
                    }
                }
            }
            for(int m=0; m<1999; m++)
            {
                dp[m] = dp_mid[m];
                dic[m] = dic_mid[m];
            }
        }
        double ans = -1.0;
        for(int i=0; i<1999; i++)
        {
            if(dp[i]== 200000) continue;
            if((double)i / (double)dp[i] > ans)
                ans = (double)i / (double)dp[i];
        }
        printf("%.3f\n", ans);
    }
    return 0;
}