P9504题解

· · 题解

题目链接 评测记录
分享一个分层图的做法。

由题意可知本题的所需生命值在路径中是单调不减的，题目本质是一个最短路。

从起点开始跑的话由于不知道魔力值和生命值，不好搞，但是最后到达终点时的魔力值和生命值一定为 0，因此可以反跑最短路。

但只当做一个 n 个点 m 条边的无向简单连通图来做会发现边权 w 的影响是会随着魔力值 k 变化的，此时一般的 Dijkstra 的做法无法保证。

如果我们将魔力和所需生命值同时记录并松弛连接的节点，该题最短路做法就是正确的。
于是我们可以想到分层图，来记录每层的魔力值。

由于边权的范围比较小，可以考虑以此为层数建分层图。

当然分层图建多了也没有关系，因为这也符合题意，所需的血量在一条路径上是单调不减的。
可以尝试下建最大的 \max_{i=1}^{m} \{w\} 层图，我懒狗直接多建了点。

最后直接遍历每层的 s 点所需生命值即可。

注意数据范围。

代码如下。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=2e4+10,MAXM=4e4+10,INF=0x3f3f3f3f,MAXW=100+5;
struct EDGE
{
    int v,w,nxt;
}edge[(MAXM<<1)*MAXW];
struct node
{
    int u,dis;
    bool operator<(const node a)const
    {
        return dis>a.dis;
    }
};
priority_queue<node> q;
int n,m,cnt,moli[MAXN*MAXW],head[MAXN*MAXW],dis[MAXN*MAXW]/*dis表示生命值*/;
bool vis[MAXN*MAXW];
inline int read()
{
    int x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
void add(int u,int v,int w)
{
    ++cnt;
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].nxt=head[u];
    head[u]=cnt;
}
void dijkstra(int s)
{
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    q.push((node){s,dis[s]});
    while(!q.empty())
    {
        node a=q.top();q.pop();
        int u=a.u;
        if(vis[u])continue;
        vis[u]=1;
        int tmoli=moli[u]+1;
        for(int i=head[u];i;i=edge[i].nxt)
        {
            int v=edge[i].v,w=edge[i].w;
            int adis=w/tmoli,tdis=adis+dis[u];
            if(tdis<dis[v])
            {
                dis[v]=tdis;
                moli[v]=tmoli;
                q.push((node){v,dis[v]});
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int s,t;
    n=read();m=read();s=read();t=read();
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read(),w=read();
        for(int j=1;j<MAXW;j++)
        {
            add(u+(j-1)*n,v+n*j,w);
            add(v+(j-1)*n,u+n*j,w);
        }
    }
    dijkstra(t);
    int ans=INF;
    for(int i=0;i<MAXW;i++)
    {
        ans=min(ans,dis[s+i*n]);
    }
    cout<<ans;
    return 0;
}