题解 P3953 【逛公园】

万弘 · 2019-11-12 22:23:07 · 题解

本人观察了大部分题解,发现真正能通过目前为止所有hack数据的不足5篇(所以也建议管理员撤下部分明显错误的题解,比如找到0环就-1的)

本人加以总结归纳,得出了可以通过到目前为止所有hack数据的做法(直接讲满分做法了):

考虑到有无穷多中方案,当且仅当1->n的一条可行路径上存在一个0环.

如何找真正意义上的0环?先标记所有连有0边的u令tag[u]=1;取出所有0边建图,统计入度,进行拓扑排序(一开始入队时加入所有入度为0且tag[u]=1的点),所有从队列中成功取出的点v标记vis1[v]=1.这样做完之后,我们删掉了所有通过0边指向0环的点.但我们这时就判断-1是不正确的,因为图上不仅有0环,还有0环通过0边指向的点.于是再取出所有0边建一个反图,再跑一次拓扑排序,取出的点标记vis2[v]=1

最后,满足tag[u]=1,vis1[u]=0,vis2[u]=0的u就在0环上.

判断u是否在可行路径上是很简单的:从1开始跑Dij,求出dis1[u],表示1到u的距离;从n开始跑Dij,求出disn[u],表示n到u的距离;最后满足dis1[u]+disn[u]\le dis1[n]+K的点就在可行路径上

综上,当且仅当存在同时满足上述两个条件的点,就有无穷多条合法路径,即需要输出-1.

接下来就是常规做法了:
f[j][u]表示从1到u,距离为dis1[u]+j的路径数
转移时,先以dis1为第一关键字,拓扑序为第二关键字递增地排序;然后对于每个点u,会对其可达的v产生f[dis1[u]+j+e[i].w-dis1[v]][v]+=f[j][u]\ (dis1[u]+j+e[i].w-dis1[v]\le K)的贡献. 注意循环要j在外层,u在内层.

理论时间复杂度O(T(m+n)logn)但实际运行却不快,最长点竟然2.5s,可能是我人菜自带大常数吧(欢迎大佬优化)

为了让更多人看到正解,也为了我2h写正解代码,1h写这篇题解,点个赞再看代码吧.

没错,210行,去掉库约160行.不过我刻意没有压行
//Wan Hong 3.0
//notebook
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>

typedef unsigned un;
typedef std::string str;
typedef int ll;
typedef std::pair<ll,ll> pll;
const ll INF=0x3f3f3f3f;
ll read()
{
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x;
}
ll min(ll a,ll b)
{
    return a<b?a:b;
}
ll max(ll a,ll b)
{
    return a>b?a:b;
}
bool umin(ll &a,ll b)
{
    if(b<a)return a=b,1;
    return 0;
}
bool umax(ll &a,ll b)
{
    if(b>a)return a=b,1;
    return 0;
}
ll abs(ll x)
{
    return x>0?x:-x;
}
/**********/
#define MAXN 100011
#define MAXM 200011
#define MAXK 51
struct Edge//邻接表存图
{
    ll v,w,nxt;
}e[MAXM];
ll cnt=0,last[MAXN];
void adde(ll u,ll v,ll w)//加边
{
    ++cnt;
    e[cnt].v=v,e[cnt].w=w;
    e[cnt].nxt=last[u],last[u]=cnt;
}
ll cu[MAXM],cv[MAXM],cw[MAXM];//拷贝边,重建图用

struct node//Dij的优先队列节点
{
    ll u,dis;
    bool operator <(const node& t)
    const
    {
        return dis>t.dis;
    }
    node(ll _u=0,ll _dis=0)
    {
        u=_u,dis=_dis;
    }
};
ll dis1[MAXN],disn[MAXN];
void Dij(ll s,ll dis[])//Dij求最短路
{
    std::priority_queue<node>q;
    dis[s]=0;q.push(node(s,dis[s]));
    while(!q.empty())
    {
        ll u=q.top().u,tmp=q.top().dis;q.pop();
        if(dis[u]!=tmp)continue;
        for(ll i=last[u];i;i=e[i].nxt)
        {
            ll v=e[i].v;
            if(umin(dis[v],dis[u]+e[i].w))
            {
                q.push(node(v,dis[v]));
            }
        }
    }
}
ll ind[MAXN],tag[MAXN],ord[MAXN],vis1[MAXN],vis2[MAXN];//入度,是否有0边,拓扑序,是否不在环上
ll n,m,k,p;
void topo(ll vis[])//拓扑排序
{
    ll now=0;
    std::queue<ll>q;
    for(ll i=1;i<=n;++i)
        if(!ind[i]&&tag[i])q.push(i);
    while(!q.empty())
    {
        ll u=q.front();q.pop();
        vis[u]=1;ord[u]=++now;
        for(ll i=last[u];i;i=e[i].nxt)
        {
            ll v=e[i].v;
            if(!--ind[v])q.push(v);
        }
    }
}
bool cmp(ll x,ll y)
{
    if(dis1[x]==dis1[y])return ord[x]<ord[y];
    return dis1[x]<dis1[y];
}
ll f[MAXK][MAXN],a[MAXN];//dp数组和dp顺序
int main()
{
    ll task=read();
    while(task--)
    {
        memset(tag,0,sizeof tag);//清空全局变量
        cnt=0;
        memset(last,0,sizeof last);
        memset(ord,0,sizeof ord);
        memset(vis1,0,sizeof vis1);memset(vis2,0,sizeof vis2);
        n=read(),m=read(),k=read(),p=read();
        for(ll i=1;i<=m;++i)//建原图
        {
            cu[i]=read(),cv[i]=read(),cw[i]=read();
            adde(cu[i],cv[i],cw[i]);
        }
        memset(dis1,0x3f,sizeof dis1);//两次Dij求最短路
        Dij(1,dis1);
        cnt=0;
        memset(last,0,sizeof last);
        for(ll i=1;i<=m;++i)
            adde(cv[i],cu[i],cw[i]);
        memset(disn,0x3f,sizeof disn);
        Dij(n,disn);
        cnt=0;//取出0边跑第一次拓扑排序
        memset(last,0,sizeof last);
        memset(ind,0,sizeof ind);
        for(ll i=1;i<=m;++i)
            if(cw[i]==0)
            {
                tag[cu[i]]=tag[cv[i]]=1;
                ++ind[cu[i]];
                adde(cv[i],cu[i],cw[i]);
            }
        topo(vis1);
        cnt=0;//取出0边跑第二次拓扑排序
        memset(last,0,sizeof last);
        memset(ind,0,sizeof ind);
        for(ll i=1;i<=m;++i)
            if(cw[i]==0)
            {
                ++ind[cv[i]];
                adde(cu[i],cv[i],cw[i]);
            }
        memset(ord,0,sizeof ord);
        topo(vis2);
        bool flag=0;
        for(ll i=1;i<=n;++i)
            if(tag[i]&&!vis1[i]&&!vis2[i]&&dis1[i]+disn[i]<=dis1[n]+k)//关键的判-1部分
            {
                flag=1;
                break;
            }
        if(flag)
        {
            puts("-1");
            continue;
        }
        cnt=0;
        memset(last,0,sizeof last);//重建原图
        for(ll i=1;i<=m;++i)
            adde(cu[i],cv[i],cw[i]);
        for(ll i=1;i<=n;++i)a[i]=i;
        std::sort(a+1,a+n+1,cmp);
        memset(f,0,sizeof f);
        f[0][1]=1%p;
        ll ans=0;
        for(ll j=0;j<=k;++j)//dp计算路径
        {
            for(ll t=1;t<=n;++t)
            {
                ll u=a[t];
                if(!f[j][u])continue;
                for(ll i=last[u];i;i=e[i].nxt)
                {
                    ll v=e[i].v,cur=dis1[u]+j+e[i].w-dis1[v];
                    if(cur<=k)f[cur][v]=(f[cur][v]+f[j][u])%p;
                }
            }
            ans=(ans+f[j][n])%p;
        }
        printf("%d\n",ans);
    }
    return 0;
}