DP+图论大毒瘤。
推荐这个博客。
先跑两遍最短路，搞掉一些无用点。
然后选出最短路上的边，做拓扑排序。
然后每层DP。
具体看代码。
用到的数组较多，记得清空。
1 #include <cstdio> 2 #include <queue> 3 #include <cstring> 4 const int N = 100010; 5 6 inline void read(int &x) { 7 x = 0; 8 char c = getchar(); 9 while(c > '9' || c < '0') { 10 c = getchar(); 11 } 12 while(c <= '9' && c >= '0') { 13 x = (x << 3) + (x << 1) + c - 48; 14 c = getchar(); 15 } 16 return; 17 } 18 19 struct Edge { 20 int nex, len, v; 21 }edge[N << 1], edge_[N << 1]; int top; 22 23 int n, m, K, MO, f[N][52]; 24 int e[N], e_[N], d[N], d_[N]; 25 bool vis[N], use_e[N << 1], use_p[N]; 26 int topo[N], in[N], TOPO; 27 28 inline void add(int x, int y, int z) { 29 edge[++top].v = y; 30 edge[top].len = z; 31 edge[top].nex = e[x]; 32 e[x] = top; 33 edge_[top].v = x; 34 edge_[top].len = z; 35 edge_[top].nex = e_[y]; 36 e_[y] = top; 37 return; 38 } 39 40 inline void SPFA() { 41 std::queue<int> Q; 42 memset(vis, 0, sizeof(vis)); 43 memset(d, 0x3f, sizeof(d)); 44 Q.push(1); 45 d[1] = 0; 46 vis[1] = 1; 47 while(!Q.empty()) { 48 int x = Q.front(); 49 Q.pop(); 50 vis[x] = 0; 51 for(int i = e[x]; i; i = edge[i].nex) { 52 int y = edge[i].v; 53 if(d[y] > d[x] + edge[i].len) { 54 d[y] = d[x] + edge[i].len; 55 if(!vis[y]) { 56 vis[y] = 1; 57 Q.push(y); 58 } 59 } 60 } 61 } 62 for(int i = 1; i <= n; i++) { 63 if(d[i] == 0x3f3f3f3f) { 64 use_p[i] = 0; 65 } 66 } 67 return; 68 } 69 70 inline void SPFA_() { 71 std::queue<int> Q; 72 memset(vis, 0, sizeof(vis)); 73 memset(d_, 0x3f, sizeof(d_)); 74 Q.push(n); 75 vis[n] = 1; 76 d_[n] = 0; 77 while(!Q.empty()) { 78 int x = Q.front(); 79 Q.pop(); 80 vis[x] = 0; 81 for(int i = e_[x]; i; i = edge_[i].nex) { 82 int y = edge_[i].v; 83 if(d_[y] > d_[x] + edge_[i].len) { 84 d_[y] = d_[x] + edge_[i].len; 85 if(!vis[y]) { 86 vis[y] = 1; 87 Q.push(y); 88 } 89 } 90 } 91 } 92 for(int i = 1; i <= n; i++) { 93 if(d_[i] == 0x3f3f3f3f) { 94 use_p[i] = 0; 95 } 96 } 97 return; 98 } 99 100 inline void solve() { 101 int x, y, z; 102 read(n); 103 read(m); 104 read(K); 105 read(MO); 106 top = 0; 107 memset(e, 0, sizeof(e)); 108 memset(e_, 0, sizeof(e_)); 109 for(int i = 1; i <= m; i++) { 110 read(x); 111 read(y); 112 read(z); 113 add(x, y, z); 114 } 115 memset(use_p, 1, sizeof(use_p)); 116 //printf("use_p %d ", use_p[2]); 117 SPFA_(); 118 SPFA(); 119 120 memset(use_e, 0, sizeof(use_e)); 121 memset(in, 0, sizeof(in)); 122 for(int i = 1; i <= m; i++) { 123 int x = edge_[i].v; 124 int y = edge[i].v; 125 if(use_p[x] && use_p[y] && d[x] + edge[i].len == d[y]) { 126 use_e[i] = 1; 127 in[y]++; 128 } 129 } 130 131 /// topo sort 132 TOPO = 0; 133 std::queue<int> Q; 134 for(int i = 1; i <= n; i++) { 135 if(!in[i]) { 136 Q.push(i); 137 } 138 } 139 while(!Q.empty()) { 140 int x = Q.front(); 141 Q.pop(); 142 topo[++TOPO] = x; 143 for(int i = e[x]; i; i = edge[i].nex) { 144 if(!use_e[i]) { 145 continue; 146 } 147 int y = edge[i].v; 148 in[y]--; 149 if(!in[y]) { 150 Q.push(y); 151 } 152 } 153 } 154 if(TOPO < n) { 155 printf("-1 "); 156 return; 157 } 158 159 /// DP 160 memset(f, 0, sizeof(f)); 161 f[1][0] = 1; 162 for(int k = 0; k <= K; k++) { 163 for(int a = 1; a <= n; a++) { 164 int x = topo[a]; 165 if(!use_p[x]) { 166 continue; 167 } 168 for(int i = e[x]; i; i = edge[i].nex) { 169 int y = edge[i].v; 170 if(!use_p[y]) { 171 continue; 172 } 173 int temp = d[x] + edge[i].len - d[y] + k; 174 if(temp > K) { 175 //printf("temp = %d > K ", temp); 176 continue; 177 } 178 //printf("f[%d][%d] += f[%d][%d] ", y, temp, x, k); 179 f[y][temp] += f[x][k]; 180 f[y][temp] %= MO; 181 //printf("= %d ", f[y][temp]); 182 } 183 } 184 } 185 186 int ans = 0; 187 for(int i = 0; i <= K; i++) { 188 ans = (ans + f[n][i]) % MO; 189 } 190 printf("%d ", ans); 191 192 return; 193 } 194 195 int main() { 196 int T; 197 read(T); 198 while(T--) { 199 solve(); 200 } 201 return 0; 202 }
感觉是我用memset最多的一次了。
有个记忆化搜索的写法，先坑着。