传送门

花了一个下午才 A 的毒瘤题

思路：

　　这题需要建两个图，一个正向图，一个反向图。

　　先在正向图上跑一遍 dijkstar ，计算出每个点到点1 的最短路径。

　　然后在反向图上开始记忆化搜索：

　　- 和动规一样，先定义 f [ i ][ j ] 表示：从点 1 到点 i 的距离为 dis [ i ] + j 的方案数。（初始值要为负，不然判断 0环的时候会出错）

　　- 对于每一条反向边（u，v，w）都有 f [ u ][ d ] = ∑ f [ u ][（dis[ u ] + d）-（dis[ v ] + w）] 。

　　　　设 lck_dis = （dis[ u ] + d）-（dis[ v ] + w）。

　　　　仔细分析会发现 lck_dis 就表示点 u 到起点 1 的距离。

　　　　这类似于最短路计数的转移，因为建的是反向边，所以要从后往前转移。

　　- 为了判断是否有毒瘤的 0边，需要开一个布尔数组 flag [ i ][ j ] 判断 dp 值是否被经过 2 次，且没有被确定，那么一定是有 0边导致的自环。

Code:

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<string>

#include<stack>

#include<vector>

#include<queue>

#include<deque>

#include<map>

#include<set>

using namespace std;

#define INF 0x3f

const int maxn=1e5+;

inline int read()

{

    int xs=,kr=;

    char ls;

    ls=getchar();

    while(!isdigit(ls))

    {

        if(ls=='-')

            kr=-;

        ls=getchar();

    }

    while(isdigit(ls))

    {

        xs=(xs<<)+(xs<<)+(ls^);

        ls=getchar();

    }

    return xs*kr;

}

int T,n,m,k,p;

long long ans;

int head_dij[maxn],head_dfs[maxn],dis[maxn],f[maxn][];

bool bo,vis[maxn],flag[maxn][];

priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;

struct hh

{

    int nex,to,w;

} t_dij[maxn<<],t_dfs[maxn<<];

inline void clear()

{

    bo=false;

    memset(head_dij,,sizeof(head_dij));

    memset(head_dfs,,sizeof(head_dfs));

    memset(dis,INF,sizeof(dis));

    memset(vis,false,sizeof(vis));

    memset(f,-,sizeof(f));

}

inline void add(int cnt,int nex,int to,int w)

{

    t_dij[cnt].to=to; t_dij[cnt].w=w;

    t_dij[cnt].nex=head_dij[nex]; head_dij[nex]=cnt;

    t_dfs[cnt].to=nex; t_dfs[cnt].w=w;

    t_dfs[cnt].nex=head_dfs[to]; head_dfs[to]=cnt;

}

inline void dijkstra(int s)

{

    dis[s]=;

    q.push(make_pair(,s));

    while (!q.empty())

    {

        int u=q.top().second;

        q.pop();

        if (vis[u]) continue;

        vis[u]=true;

        for (int i=head_dij[u];i;i=t_dij[i].nex)

        {

            int v=t_dij[i].to,w=t_dij[i].w;

            if (!vis[v]&&dis[v]>dis[u]+w)

            {

                dis[v]=dis[u]+w;

                q.push(make_pair(dis[v],v));

            }

        }

    }

}

int dfs(int u,int d)

{

    if (flag[u][d])

    {

        bo=true;

        return ;

    }

    if (~f[u][d]) return f[u][d];

    flag[u][d]=true;f[u][d]=;

    for (int i=head_dfs[u];i;i=t_dfs[i].nex)

    {

        if(bo) break;

        int v=t_dfs[i].to,w=t_dfs[i].w;

        int lck_dis=(dis[u]+d)-(w+dis[v]);

        if (lck_dis>=) f[u][d]=(f[u][d]+dfs(v,lck_dis))%p;

    }

    flag[u][d]=false;

    if (u==&&!d) return ++f[u][d];

    return f[u][d];

}

int x,y,z;

int main()

{

    //freopen("park.in","r",stdin);

    //freopen("park.out","w",stdout);

    T=read();

    while (T--)

    {

        clear();

        n=read();m=read();k=read();p=read();

        for(int i=;i<=m;i++)

        {

            x=read();y=read();z=read();

            add(i,x,y,z);

        }

        dijkstra();

        ans=dfs(n,)%p;

        for(int i=;i<=k;i++)

        {

            if(bo) break;

            ans=(ans+dfs(n,i))%p;

        }

        if(bo) printf("-1\n");

        else printf("%lld\n",ans);

    }

return ;

}

注：在 dfs 中，if ( ~ f [ u ][ d ] ) ⇔ if ( f [ u ][ d ] ≥ 0 ) 。有助于卡常

巴特西

P3953 逛公园

传送门

思路：

Code:

最新文章

热门文章