T124857【逃离矿洞】题解

SfumatoCannon_ · 2020-03-09 21:31:51 · 个人记录

T5:
先从头到尾读一遍题，主要有以下几点：

每条边有两个权值 s , h.
每个点有一个权值 a_i. 到达某个点后， h_{tot} 将更新为 h_{tot}-a_i，同时 a_i 将置为0.
要从1号点到达 n 号点，同时使得 s_{tot}\cdot h_{tot} 最小。

为了表述方便，我们将吃掉食物之前消耗的饥饿值记为 h_1 , 吃掉食物之后的实际消耗的饥饿值记为 h_2.
很容易看出，这题和最短路脱不了关系。但标准的最短路只有边权，没有点权。
于是，我们会有一个很自然的想法：能否把点权的条件去掉呢？这样最短路就好写了。接着联想到：能否在插入边时，以 (s,h_2) 作为权值插入，而代替原本的 (s,h_1) 呢？
但如果这么做，经过一个点后，a_i 置为0的操作又怎么实现呢？

看一眼数据范围，我们发现一个十分有用的东西：

a_{max}\leqslant h_{min}

这表明，从点到点之间行走，吃掉食物所恢复的饥饿值是不会比原先消耗的饥饿值大的。即，a_i\leqslant h_1.
又因为 h_2=h_1-a_i,
所以我们就得到了：h_2\geqslant 0. 又因为 s>0,
从而，我们可以保证：以上文所述的方法建图，一定是非负权图.
既然它是非负权图，那么跑一遍最短路，每个点必然最多只经过一次。
因此，a_i 置为0的操作，可有可无。

接下来怎么做也很简单了。将松弛操作的判断条件改一下即可。
code:

#include <cstdio>
#include <queue>
using namespace std;
#define ll long long
#define inf 0x7fffffff
struct node
{
    ll num,dis1,dis2;
    bool operator <(const node &x)const
    {
        return x.dis1*x.dis2<dis1*dis2;
    }
};
struct Edge
{
    ll next,to,dis1,dis2;
}bian[400001];
ll h[100001],n,m,a[100001];
bool vis[100001];
ll Ans1[100001],Ans2[100001];
void AddEdge(ll x,ll y,ll t1,ll t2,ll id)
{
    bian[id].dis1=t1;
    bian[id].dis2=t2;
    bian[id].next=h[x];
    bian[id].to=y;
    h[x]=id;
}
void dijkstra(ll start)
{
    priority_queue<node> Q;
    node T;
    ll i,p;
    for (i=1;i<=n;i++)
    {
        Ans1[i]=inf;
        Ans2[i]=inf;
        vis[i]=false;
    }
    Ans1[start]=Ans2[start]=0;
    Q.push((node){start,0,0});
    while (!Q.empty())
    {
        T=Q.top();
        Q.pop();
        p=T.num;
        if (vis[p]) continue;
        vis[p]=true;
        for (i=h[p];i;i=bian[i].next)
        {
            if (Ans1[bian[i].to]*Ans2[bian[i].to]>(Ans1[p]+bian[i].dis1)*(Ans2[p]+bian[i].dis2))
            {
                Ans1[bian[i].to]=Ans1[p]+bian[i].dis1;
                Ans2[bian[i].to]=Ans2[p]+bian[i].dis2;
                if (!vis[bian[i].to])
                    Q.push((node){bian[i].to,Ans1[bian[i].to],Ans2[bian[i].to]});
            }
        }
    }
}
int main()
{
    ll i,x,y,s,h;
    scanf("%lld%lld",&n,&m);
    for (i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for (i=1;i<=m;i++)
    {
        scanf("%lld%lld%lld%lld",&x,&y,&s,&h);
        AddEdge(x,y,s,h-a[y],i*2-1);
        AddEdge(y,x,s,h-a[x],i*2);
    }
    dijkstra(1);
    if (Ans1[n]*Ans2[n]==4611686014132420609) printf("-1");
    else printf("%lld",Ans1[n]*Ans2[n]);
    return 0;
}