高玩小Q不仅喜欢玩寻宝游戏,还喜欢一款升级养成类游戏。在这个游戏的世界地图中一共有n个城镇,编号依次为1到n。

这些城镇之间有m条单向道路,第i 条单项道路包含四个参数ui,vi,ai,biui,vi,ai,bi,表示一条从ui号城镇出发,在vivi号城镇结束的单向道路,因为是单向道路,这不意味着小Q可以从vivi沿着该道路走到uiui。小Q的初始等级levellevel为1,每当试图经过一条道路时,需要支付cost=log2(level+ailevel)cost=log_2(\frac{level+a_i}{level})点积分,并且经过该道路后,小Q的等级会提升aiai级,到达level+ailevel+a_i级。但是每条道路都会在一定意义上歧视低消费玩家,准确地说,如果该次所需积分costbicost bi,那么小Q不能经过该次道路,也不能提升相应的等级。

注意:本游戏中等级为正整数,但是积分可以是任意实数。

小Q位于1号城镇,等级为1,现在为了做任务要到n号城镇去。这将会是一次奢侈的旅行,请写一个程序帮助小Q找到需要支付的总积分最少的一条路线,或判断这是不可能的。

链接 🔗

「HDU 6290」奢侈的旅行

题解 ❓

将题目中的公式整理后可以发现
所得i=1nai\sum_{i=1}^{n} a_i 越小,能到达的点越多,并且积分越少
因此我们可以将积分作为权值,跑最短路,跑的过程中判断 bib_i是否满足
最后统计答案即可

代码

const ll N = 2e5+10;
const ll mod = 998244353;
struct
{
    ll v,net,s,c;
}e[N<<2];
ll f[N],tot;
void insert(ll u,ll v,ll a, ll b)
{
    e[++tot].net = f[u];
    e[tot].v = v;
    e[tot].s = b;
    e[tot].c = a;
    f[u] = tot;
}
ll d[N];
int main()
{
//    __IN;__OUT
    ll T;RLL(T);
    while(T--)
    {
        ll n,m;RLL2(n,m);
        MM(f,-1);tot= 0;
        FOR(i,1,m)
        {
            ll u,v,a,b;
            RLL4(u,v,a,b);insert(u,v,a,b);
        }
        MM(d,233);
        priority_queue<P,vector<P>,greater<P> > que;
        d[1] = 1; que.push(P(1,1));
        while(!que.empty())
        {
            P p = que.top(); que.pop();
            ll x = p.ND,y = p.ST;
            if(y > d[x]) continue;
            for(auto i=f[x];i+1;i=e[i].net)
            {
                ll v = e[i].v;
                if(d[v] <= d[x] + e[i].c || log2( (d[x]  + e[i].c * 1.0)/d[x] * 1.0) < e[i].s) continue;
                d[v] = d[x] + e[i].c;
                que.push(P(d[v],v));
            }
        }
//        FOR(i,1,n) PLP(d[i]);

        if(d[n] == d[n+1]) PS("-1");
        else PLN((ll)log2(d[n]));
    }
    return 0;
}