做题记录：
花了3个小时写了个5K代码（如果是noip现场肯定时间不够了），本地跑大样例跑3秒一组？
结果交上去一看70分，最慢点800ms左右，所有有0边的都错了？
然而事实上这代码这么长大部分就是为了特判0边。。。看来即使noip发现码量不对也要尽快放弃
下数据一测...单组数据就A了？
调了1个小时，终于调出来了，就改了一行...
错误记录：241行上界错误，t2[0]写成n
自己的(假)做法：（说不定其实有错？）
先求最短路。设d[i]表示1到i的最短路
首先判-1。可以发现，如果存在一条从1到n过某点u的长度不超过d[n]+K的路径，且u在一个0环（由全0边组成的环）上面，就-1了，否则就不-1
（以上可以通过再求所有点到n最短路，以及对由仅保留0边得到的图做tarjan求强连通分量完成）
否则，考虑一个dp。an[i][j]表示到i点距离为d[i]+j的路径条数。跟最短路计数挺像。但是，可以发现转移顺序似乎有点问题？
考虑按j来划分“层”，尽量使得转移在层间进行，避免转移成环；要保证同层内按照转移的“拓扑序”进行；显然仅当d[u] + (u,v)边的长度 = d[v]时会发生u到v的同层转移
设(u,v)边的长度=dis(u,v)
首先，如果没有0权边，那么显然只要按照d[i]的值从小到大将各个点排序，同层内按这个顺序转移即可。因为此时如果d[u]+dis(u,v)=d[v]，那么d[u]<d[v]
如果有0权边，就不能这么干了。
对于任意两点u,v，它们间有边(u,v,w)，如果w>0，那么仍然满足上述条件；如果w=0，那么有两种情况：
1.d[u]>d[v]；此时u到v不可能发生同层转移
2.d[u]=d[v]；此时可能发生同层内转移，因此应当保证u在v之前转移
那么就明显了，对于d[i]相等的点，应该按照“只保留0边后的图的拓扑序中点的位置”从小到大排序
可是似乎不一定有这个拓扑序？首先，如果有一点满足u“存在一条从1到n过u的长度不超过d[n]+K的路径”，且u在一个0环上，那么就-1了，不用dp；如果u不满足这个条件，但u在一个0环上，那么可以不管这个u
设当且仅当'存在一条从1到n过u的长度不超过d[n]+K的路径'时，ok[u]=true；否则ok[u]=false
所以，“只保留0边后的图的拓扑序中点的位置”应该改为“只保留0边与所有满足ok[u]=true的点u后的图的拓扑序中点的位置”
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<vector> 5 #include<queue> 6 using namespace std; 7 #define fi first 8 #define se second 9 #define pb push_back 10 typedef long long ll; 11 typedef unsigned long long ull; 12 struct pii 13 { 14 int fi,se; 15 pii():fi(0),se(0){} 16 pii(int a,int b):fi(a),se(b){} 17 }; 18 19 bool operator<(const pii &a,const pii &b) 20 { 21 return a.fi>b.fi;//||(a.fi==b.fi&&a.se<b.se); 22 } 23 24 /* 25 bool operator>(const pii &a,const pii &b) 26 { 27 return a.fi<b.fi;//||(a.fi==b.fi&&a.se>b.se); 28 } 29 */ 30 typedef priority_queue<pii> pq; 31 struct E 32 { 33 int to,d,nxt; 34 }e[200010]; 35 int f1[100010],ne; 36 int n,m,K,md; 37 bool ok[100010]; 38 //inline int mul(int x,int y){return ll(x)*y%md;} 39 //inline int add(int x,int y){return (x+y)%md;} 40 inline void add(int &x,int y){(x+=y)%=md;} 41 namespace OK 42 { 43 44 int dfn[100010],dfc; 45 int s[100010],tp; 46 int sccnum[100010],cnt; 47 int sz[100010]; 48 int dfs(int u) 49 { 50 int lowu=dfn[u]=++dfc,lowv,v,k; 51 s[++tp]=u; 52 for(k=f1[u];k;k=e[k].nxt) 53 if(e[k].d==0) 54 { 55 v=e[k].to; 56 if(!dfn[v]) 57 { 58 lowv=dfs(v); 59 lowu=min(lowu,lowv); 60 } 61 else if(!sccnum[v]) 62 lowu=min(lowu,dfn[v]); 63 } 64 if(lowu==dfn[u]) 65 { 66 ++cnt; 67 while(tp&&s[tp]!=u) sccnum[s[tp--]]=cnt; 68 sccnum[s[tp--]]=cnt; 69 } 70 return lowu; 71 } 72 void work() 73 { 74 int i; 75 dfc=0;tp=0; 76 memset(dfn+1,0,sizeof(dfn[0])*n); 77 memset(sccnum+1,0,sizeof(sccnum[0])*n); 78 memset(sz+1,0,sizeof(sz[0])*cnt); 79 cnt=0; 80 for(i=1;i<=n;++i) 81 if(!dfn[i]) 82 dfs(i); 83 for(i=1;i<=n;++i) 84 ++sz[sccnum[i]]; 85 } 86 87 } 88 namespace Dij1 89 { 90 91 pq q; 92 int d[100010]; 93 bool vis[100010]; 94 void dij() 95 { 96 int k,u,v;pii t; 97 memset(d+1,0x3f,sizeof(d[0])*n); 98 memset(vis+1,0,sizeof(vis[0])*n); 99 q.push(pii(0,1));d[1]=0; 100 while(!q.empty()) 101 { 102 t=q.top();q.pop(); 103 u=t.se; 104 if(vis[u]) continue; 105 vis[u]=1; 106 for(k=f1[u];k;k=e[k].nxt) 107 { 108 v=e[k].to; 109 if(d[v]>d[u]+e[k].d) 110 { 111 d[v]=d[u]+e[k].d; 112 q.push(pii(d[v],v)); 113 } 114 } 115 } 116 } 117 118 } 119 namespace Dij2 120 { 121 122 E e[200010]; 123 int f1[100010],ne; 124 void me(int x,int y,int z) 125 { 126 e[++ne].to=y;e[ne].nxt=f1[x];f1[x]=ne;e[ne].d=z; 127 } 128 pq q; 129 int d[100010]; 130 bool vis[100010]; 131 void dij() 132 { 133 int k,u,v;pii t; 134 memset(d+1,0x3f,sizeof(d[0])*n); 135 memset(vis+1,0,sizeof(vis[0])*n); 136 q.push(pii(0,n));d[n]=0; 137 while(!q.empty()) 138 { 139 t=q.top();q.pop(); 140 u=t.se; 141 if(vis[u]) continue; 142 vis[u]=1; 143 for(k=f1[u];k;k=e[k].nxt) 144 { 145 v=e[k].to; 146 if(d[v]>d[u]+e[k].d) 147 { 148 d[v]=d[u]+e[k].d; 149 q.push(pii(d[v],v)); 150 } 151 } 152 } 153 } 154 155 } 156 namespace DP 157 { 158 159 int t2[100010]; 160 namespace T 161 { 162 163 queue<int> q; 164 int in[100010]; 165 void work() 166 { 167 int i,k,u; 168 memset(in+1,0,sizeof(in[0])*n); 169 t2[0]=0; 170 for(i=1;i<=n;++i) 171 if(ok[i]) 172 { 173 for(k=f1[i];k;k=e[k].nxt) 174 if(ok[e[k].to]&&e[k].d==0) 175 ++in[e[k].to]; 176 } 177 for(i=1;i<=n;++i) 178 if(ok[i]&&!in[i]) 179 q.push(i); 180 while(!q.empty()) 181 { 182 u=q.front();q.pop(); 183 t2[++t2[0]]=u; 184 for(k=f1[u];k;k=e[k].nxt) 185 if(ok[e[k].to]&&e[k].d==0) 186 { 187 --in[e[k].to]; 188 if(!in[e[k].to]) q.push(e[k].to); 189 } 190 } 191 } 192 193 } 194 int ps[100010]; 195 int t1[100010]; 196 using Dij1::d; 197 bool c1(int a,int b) 198 { 199 return d[a]<d[b]||(d[a]==d[b]&&ps[a]<ps[b]); 200 } 201 int an[100010][51]; 202 namespace E2 203 { 204 205 E e[200100]; 206 int f1[100010],ne; 207 void me(int x,int y,int z) 208 { 209 e[++ne].to=y;e[ne].nxt=f1[x];f1[x]=ne;e[ne].d=z; 210 } 211 void work() 212 { 213 int i,j,k,u,v,y; 214 //printf("1t%d ",t1[1]); 215 an[1][0]=1; 216 for(j=0;j<=K;++j) 217 { 218 for(i=1;i<=t1[0];++i) 219 { 220 u=t1[i]; 221 for(k=f1[u];k;k=e[k].nxt) 222 { 223 v=e[k].to; 224 if(d[u]+j+e[k].d<=d[v]+K) 225 { 226 y=d[u]+j+e[k].d-d[v]; 227 add(an[v][y],an[u][j]); 228 } 229 } 230 } 231 } 232 } 233 234 } 235 void dp() 236 { 237 int i,j,k; 238 memset(an+1,0,sizeof(an[0])*n); 239 memset(ps+1,0,sizeof(ps[0])*n); 240 T::work(); 241 for(i=1;i<=t2[0];++i)// 242 ps[t2[i]]=i; 243 t1[0]=0; 244 for(i=1;i<=n;++i) 245 if(ok[i]) 246 t1[++t1[0]]=i; 247 sort(t1+1,t1+t1[0]+1,c1); 248 memset(E2::f1+1,0,sizeof(E2::f1[0])*n); 249 E2::ne=0; 250 for(i=1;i<=n;++i) 251 if(ok[i]) 252 { 253 for(k=f1[i];k;k=e[k].nxt) 254 if(ok[e[k].to]) 255 { 256 E2::me(i,e[k].to,e[k].d); 257 } 258 } 259 E2::work(); 260 int ans=0; 261 for(j=0;j<=K;++j) 262 add(ans,an[n][j]); 263 printf("%d ",ans); 264 } 265 266 } 267 /* 268 namespace DP 269 { 270 271 queue<int> q; 272 using Dij::d; 273 //点的定义：(i,j)表示从1走d[i]+j的距离到i 274 int an[100010][51];//an[i][j]表示到(i,j)的路径条数 275 bool vis[100010][51]; 276 void dp() 277 { 278 memset(vis+1,0,sizeof(vis[0])*n); 279 memset(an+1,0,sizeof(an[0])*n); 280 int x,u,v; 281 while(!q.empty()) 282 { 283 u=q.front();q.pop(); 284 for(k=f1[u];k;k=e[k].nxt) 285 { 286 v=e[k].to; 287 if(d[u]+e[k].d<=d[v]+K) 288 { 289 y=d[u]+e[k].d-d[v]; 290 add(an[v][y],an[u][x]); 291 } 292 } 293 } 294 for(j=1;j<=K;++j) 295 { 296 297 while(!q.empty()) 298 { 299 t=q.front();q.pop(); 300 u=t.fi;x=t.se; 301 for(k=f1[u];k;k=e[k].nxt) 302 { 303 v=e[k].to; 304 if(d[u]+x+e[k].d<=d[v]+K) 305 { 306 y=d[v]+K-d[u]-x-e[k].d; 307 add(an[v][y],an[u][x]); 308 } 309 } 310 } 311 } 312 313 } 314 */ 315 int T; 316 int main() 317 { 318 //freopen("/tmp/test1.in","r",stdin); 319 //freopen("/tmp/park6.in","r",stdin); 320 //freopen("/tmp/ex_park2.out","w",stdout); 321 int i,x,y,z; 322 scanf("%d",&T); 323 while(T--) 324 { 325 scanf("%d%d%d%d",&n,&m,&K,&md); 326 memset(f1+1,0,sizeof(f1[0])*n); 327 memset(ok+1,0,sizeof(ok[0])*n); 328 ne=0; 329 memset(Dij2::f1+1,0,sizeof(Dij2::f1[0])*n); 330 Dij2::ne=0; 331 for(i=1;i<=m;++i) 332 { 333 scanf("%d%d%d",&x,&y,&z); 334 e[++ne].to=y;e[ne].nxt=f1[x];f1[x]=ne;e[ne].d=z; 335 Dij2::me(y,x,z); 336 } 337 OK::work(); 338 Dij1::dij();Dij2::dij(); 339 { 340 int *d1=Dij1::d,*d2=Dij2::d; 341 for(i=1;i<=n;++i) 342 if(d1[i]+d2[i]<=d1[n]+K) 343 { 344 ok[i]=1; 345 if(OK::sz[OK::sccnum[i]]>1) 346 { 347 puts("-1"); 348 goto xx1; 349 } 350 } 351 } 352 DP::dp(); 353 xx1:; 354 } 355 return 0; 356 }
一查题解，发现貌似只要按照上面类似的方法建一个分层图，直接对这个分层图跑拓扑排序以及判环就行了？