DP+图论大毒瘤。
推荐这个博客。
先跑两遍最短路，搞掉一些无用点。
然后选出最短路上的边，做拓扑排序。
然后每层DP。
具体看代码。
用到的数组较多，记得清空。
#include <cstdio>
#include <queue>
#include <cstring>
const int N = ; inline void read(int &x) {
x = ;
char c = getchar();
while(c > '' || c < '') {
c = getchar();
}
while(c <= '' && c >= '') {
x = (x << ) + (x << ) + c - ;
c = getchar();
}
return;
} struct Edge {
int nex, len, v;
}edge[N << ], edge_[N << ]; int top; int n, m, K, MO, f[N][];
int e[N], e_[N], d[N], d_[N];
bool vis[N], use_e[N << ], use_p[N];
int topo[N], in[N], TOPO; inline void add(int x, int y, int z) {
edge[++top].v = y;
edge[top].len = z;
edge[top].nex = e[x];
e[x] = top;
edge_[top].v = x;
edge_[top].len = z;
edge_[top].nex = e_[y];
e_[y] = top;
return;
} inline void SPFA() {
std::queue<int> Q;
memset(vis, , sizeof(vis));
memset(d, 0x3f, sizeof(d));
Q.push();
d[] = ;
vis[] = ;
while(!Q.empty()) {
int x = Q.front();
Q.pop();
vis[x] = ;
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(d[y] > d[x] + edge[i].len) {
d[y] = d[x] + edge[i].len;
if(!vis[y]) {
vis[y] = ;
Q.push(y);
}
}
}
}
for(int i = ; i <= n; i++) {
if(d[i] == 0x3f3f3f3f) {
use_p[i] = ;
}
}
return;
} inline void SPFA_() {
std::queue<int> Q;
memset(vis, , sizeof(vis));
memset(d_, 0x3f, sizeof(d_));
Q.push(n);
vis[n] = ;
d_[n] = ;
while(!Q.empty()) {
int x = Q.front();
Q.pop();
vis[x] = ;
for(int i = e_[x]; i; i = edge_[i].nex) {
int y = edge_[i].v;
if(d_[y] > d_[x] + edge_[i].len) {
d_[y] = d_[x] + edge_[i].len;
if(!vis[y]) {
vis[y] = ;
Q.push(y);
}
}
}
}
for(int i = ; i <= n; i++) {
if(d_[i] == 0x3f3f3f3f) {
use_p[i] = ;
}
}
return;
} inline void solve() {
int x, y, z;
read(n);
read(m);
read(K);
read(MO);
top = ;
memset(e, , sizeof(e));
memset(e_, , sizeof(e_));
for(int i = ; i <= m; i++) {
read(x);
read(y);
read(z);
add(x, y, z);
}
memset(use_p, , sizeof(use_p));
//printf("use_p %d \n", use_p[2]);
SPFA_();
SPFA(); memset(use_e, , sizeof(use_e));
memset(in, , sizeof(in));
for(int i = ; i <= m; i++) {
int x = edge_[i].v;
int y = edge[i].v;
if(use_p[x] && use_p[y] && d[x] + edge[i].len == d[y]) {
use_e[i] = ;
in[y]++;
}
} /// topo sort
TOPO = ;
std::queue<int> Q;
for(int i = ; i <= n; i++) {
if(!in[i]) {
Q.push(i);
}
}
while(!Q.empty()) {
int x = Q.front();
Q.pop();
topo[++TOPO] = x;
for(int i = e[x]; i; i = edge[i].nex) {
if(!use_e[i]) {
continue;
}
int y = edge[i].v;
in[y]--;
if(!in[y]) {
Q.push(y);
}
}
}
if(TOPO < n) {
printf("-1\n");
return;
} /// DP
memset(f, , sizeof(f));
f[][] = ;
for(int k = ; k <= K; k++) {
for(int a = ; a <= n; a++) {
int x = topo[a];
if(!use_p[x]) {
continue;
}
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(!use_p[y]) {
continue;
}
int temp = d[x] + edge[i].len - d[y] + k;
if(temp > K) {
//printf("temp = %d > K \n", temp);
continue;
}
//printf("f[%d][%d] += f[%d][%d] ", y, temp, x, k);
f[y][temp] += f[x][k];
f[y][temp] %= MO;
//printf("= %d \n", f[y][temp]);
}
}
} int ans = ;
for(int i = ; i <= K; i++) {
ans = (ans + f[n][i]) % MO;
}
printf("%d\n", ans); return;
} int main() {
int T;
read(T);
while(T--) {
solve();
}
return ;
}
AC代码
感觉是我用memset最多的一次了。
有个记忆化搜索的写法，先坑着。