[NOIP2017]逛公园

发表于 | 分类于
字数统计: 716 | 阅读时长 ≈ 4

当年天真的我以为最短路图是有环的，然后翻了车

首先跑一遍的最短路，记为
用记录点，距离的方案数
转移方程如下

这里的是反图上的边
答案就是，初始化所有为1

对于0 环，比较好的一种处理方式是记忆优化搜索
当处理时，再次搜到，则说明图中存在0 环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
const int N=100050,rt=1;
const int INF=1<<30;
int n,m,mod,K,d[N];
int w[N<<2],vis[N];
int dp[N][55],used[N][55];
queue<int> Q;
vector<int> e[N],g[N],r[N],f[N];
inline int read()
{
    register int x=0,t=1;
    register char ch=getchar();
    while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if (ch=='-') t=-1,ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
    return x*t;
}
void init()
{
    memset(vis,0,sizeof(vis));
    memset(dp,0,sizeof(dp));
    memset(used,0,sizeof(used));
    for(int i=0;i<=n;i++) d[i]=INF;
    for(int i=1;i<=n;i++) e[i].clear();
    for(int i=1;i<=n;i++) g[i].clear();
    for(int i=1;i<=n;i++) r[i].clear();
    for(int i=1;i<=n;i++) f[i].clear();
}
void add(int u,int v,int val)
{
    e[u].push_back(v);
    g[u].push_back(val);
    r[v].push_back(u);
    f[v].push_back(val);
}
void calc(int o)
{
    int ls=w[o<<1],rs=w[o<<1|1];
    w[o]=!vis[ls]*ls+!vis[rs]*rs;
    if (vis[ls]+vis[rs]) return;
    w[o]=d[ls]<d[rs]?ls:rs;
}
void build(int o,int l,int r)
{
    if (l==r) {w[o]=r;return;}
    int mid=(l+r)>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    calc(o);
}
void modify(int o,int l,int r,int k)
{
    if (l==r) return;
    int mid=(l+r)>>1;
    if (k<=mid) modify(o<<1,l,mid,k);
    if (k>mid) modify(o<<1|1,mid+1,r,k);
    calc(o);
}
void Dijkstra(int s)
{
    build(1,1,n);
    d[s]=0,modify(1,1,n,s);
    while (d[w[rt]]!=INF)
    {
        int x=w[rt];
        for(int i=0;i<e[x].size();i++)
        {
            int to=e[x][i],val=g[x][i];
            if (d[x]+val<d[to])
            {
                d[to]=d[x]+val;
                modify(1,1,n,to);
            }
        }
        vis[x]=1,modify(1,1,n,x);
    }
}
int dfs(int o,int k)
{
    if (used[o][k]) return -1;
    if (dp[o][k]) return dp[o][k];
    if (o==1) dp[o][k]=1;
    used[o][k]=1;
    for(int i=0;i<r[o].size();i++)
    {
        int to=r[o][i];
        int val=d[to]+f[o][i]-d[o];
        if (val<=k) 
        {
            if (dfs(to,k-val)==-1) return -1;
            dp[o][k]=(dp[o][k]+dp[to][k-val])%mod;
        }
    }
    used[o][k]=0;
    return dp[o][k];
}
int main()
{
    int T=read();
    while (T--)
    {
        n=read(),m=read();
        K=read(),mod=read();
        init();
        for(int i=1;i<=m;i++)
        {
            int u=read(),v=read();
            add(u,v,read());
        }
        Dijkstra(1);
        printf("%d\n",dfs(n,K));	
    }
    return 0;
}