P3953 逛公园

题目：传送门

思路：

​ 定义⼀条路径 (X…Y) 的冗余度为它的长度减去 X…Y 的最短路长度，那么这题就是求1到N的冗余度小于k的路径的条数。我们定义 d p [ i ] [ j ] dp[i][j] dp[i][j] 代表1到 i 的冗余度等于 j 的路径的条数。对于一条有u到v的边表示为W(u,v)，我们定义函数 p ( u , v ) = w ( u , v ) + d i s [ u ] + d i t [ v ] − d i s [ T ] p(u,v)=w(u,v)+dis[u]+dit[v]-dis[T] p(u,v)=w(u,v)+dis[u]+dit[v]−dis[T] 。那么 d p [ v ] [ j ] = S U M ( d p [ u ] [ j − p ( u , v ) ] ) dp[v][j]=SUM(dp[u][j-p(u,v)]) dp[v][j]=SUM(dp[u][j−p(u,v)]) ,这个函数的意义是S到T的路径中走(u,v)这条边浪费的长度。其中 u 是后驱为v的边的前驱顶点，边权为w。

​ 这题我们主要注意两点，第一点即零环无解，第二点是确定DP顺序，使得DP顺序是DP图的一个拓扑序(满足无后效性)。

​ 第一点因为数据量较大，我们可以考虑把所有0边都提出来，判断是否存在环即可。

​ 第二点我们可以根据先从小到大枚举冗余度k，在排除第一点的条件下，因为冗余度为0的路径不可能是一个环，对于冗余度不为0的边，我们不用管(因为我们是枚举是k从大到小)，对于浪费度为0的边(这些边只可能是到v的最短路上的边，非零边和零边)，在最短路上的边我们可以根据dis值从小到大来确定dp顶点顺序。对于dis值相等且这两个顶点有一个冗余度为0的边，即零边。我们需要额外的用另一种方法确定他们的dp顺序，我们可以在前面第一点的时候求零的顶点拓扑序列设为id，这样的话得到了零边的更新方式。

​ So最后我们只需按照dis从小到大排序，dis相等的按照id从小到大排序即可，这个就是我们从小到大枚举冗余度k之后枚举顶点的dp顺序。

代码：

#include<bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
//const ll mod=1e9+7;
const ll inf=0x3f3f3f3f3f3f3f3f;//0x3f3f3f3f
//const int inf=0x3f3f3f3f;//0x3f3f3f3f
ll n,m,K,MOD;
struct Edge{
ll u,v,w;
};
Edge edge[200000+5];
ll dis[200000+5],id[200005];
vector<P> adja[200000+5];
ll dp[200005][55];
struct KA{
ll dis,id,u;
bool operator <( const KA &other) const
{
    if(dis!=other.dis) return dis<other.dis;
    return id<other.id;
}
};
ll have[200000+5],degree[200000+5];
bool haveZeroC()
{
    for(ll i=0;i<=n;++i) have[i]=0,degree[i]=0;
    for(ll i=0;i<m;++i){
        ll u=edge[i].u,v=edge[i].v,w=edge[i].w;
        if(w==0){
            have[u]=have[v]=1;
            degree[v]++;
        }
    }
    stack<ll> tak;
    for(ll i=1;i<=n;++i){
        if(have[i]&&degree[i]==0)
            tak.push(i);
    }
    ll tot=0;
    while(!tak.empty())
    {
        ll u=tak.top();tak.pop();
        id[u]=tot++;
        for(P &e:adja[u]){
            ll v=e.first,w=e.second;
            if(w==0){
                degree[v]--;
                if(degree[v]==0){
                    tak.push(v);
                }
            }
        }
    }
    for(ll i=1;i<=n;++i){
        if(have[i]&&degree[i]){
                return true;
        }
    }
    return false;
}
KA ka[200000+5];
void dijstra()
{

    priority_queue<P,vector<P>,greater<P> > qqe;
    for(ll i=1;i<=n;++i) dis[i]=inf;

    dis[1]=0;
    qqe.push({0,1});
    while(!qqe.empty()){
        P p=qqe.top();qqe.pop();
        if(p.first>dis[p.second]) continue;
        ll u=p.second;
// cout<<"u:zv"<<u<<endl;
        for(P &e:adja[u]){
            ll v=e.first,w=e.second;
// if(!w) id[v]=max(id[u]+1,dis[v]);
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                qqe.push({dis[v],v});
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    ll t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m>>K>>MOD;
        for(ll i=1;i<=n;++i) adja[i].clear();
        for(ll i=0;i<m;++i) cin>>edge[i].u>>edge[i].v>>edge[i].w;
        for(ll i=0;i<m;++i){
            adja[edge[i].u].push_back({edge[i].v,edge[i].w});
        }
        if(haveZeroC()){
            cout<<-1<<endl;
            continue ;
        }
        dijstra();
// SPFA();
        for(ll i=1;i<=n;++i){
            ka[i].dis=dis[i];
            ka[i].u=i;
            ka[i].id=id[i];
        }
        sort(ka+1,ka+n+1);
        for(ll i=1;i<=n;++i) for(ll k=0;k<=K;++k) dp[i][k]=0;
        dp[1][0]=1;
        for(ll k=0;k<=K;++k)
        {
            for(ll i=1;i<=n;++i){
                ll u=ka[i].u;
                if(!dp[u][k]) continue;
                for(P &e:adja[u]){
                    ll v=e.first,w=e.second;
                    ll rem=dis[u]+w-dis[v];
// cout<<"---"<<rem<<endl;
                    if(rem+k>K) continue;
                    dp[v][rem+k]+=dp[u][k];
                    dp[v][rem+k]%=MOD;
                }
            }
        }
        ll ans=0;
        for(ll i=0;i<=K;++i){
            ans=(ans+dp[n][i])%MOD;
        }
        cout<<ans<<endl;
    }
    return 0;
}