BZOJ3417 : Poi2013 Tales of seafaring
of
2023-09-11 14:15:04 时间
若x到y走k步可行,那么走k+2步也可行
以每个点为起点,BFS处理出到每个点走了奇数步、偶数步的最短路
对于一次询问,如果d不小于相应奇偶性的最短路,则可行
特判:对于孤立点,无论怎么走都不可行
#include<cstdio> const int N=10010,Q=1000010; int n,m,k,i,j,x,y,z,g[N],nxt[N],v[N],ed,G[N],NXT[Q],V[Q],W[Q],ED,dis[N][2],pos[N][2],q[N][2],h,t; inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';} inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;} inline void ADD(int x,int y,int z){V[++ED]=y;W[ED]=z;NXT[ED]=G[x];G[x]=ED;} inline void bfs(int x,int y,int z){if(pos[x][y]<i)pos[x][y]=i,dis[x][y]=z,q[++t][0]=x,q[t][1]=y;} int main(){ read(n),read(m),read(k); while(m--)read(x),read(y),add(x,y),add(y,x); while(k--)read(x),read(y),read(z),ADD(x,y,z); for(i=1;i<=n;i++)if(G[i]){ h=1,t=0,bfs(i,0,0); while(h<=t)for(j=g[x=q[h][0]],y=q[h++][1];j;j=nxt[j])bfs(v[j],y^1,dis[x][y]+1); for(j=G[i];j;j=NXT[j])if((V[j]!=i||g[i])&&pos[V[j]][W[j]&1]==i&&dis[V[j]][W[j]&1]<=W[j])V[j]=0; } for(i=1;i<=ED;i++)puts(V[i]?"NIE":"TAK"); return 0; }
相关文章
- How to make a dropdown list of all cultures (but no repeats)
- How do I remove the first characters of a specific column in a table?
- The implementation of iterators in C# and its consequences (part 1) Raymond Chen
- Download and Installation of Kibana
- comparison of floating point numbers with equality operator. possible loss of precision while rounding values
- English Voice of <<Beautiful now>>
- Correct the classpath of your application so that it contains a single, compatible version of…
- hdoj 5087 Revenge of LIS II 【第二长单调递增子】
- [LeetCode] 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance 阈值距离内邻居最少的城市
- [LeetCode] 893. Groups of Special-Equivalent Strings 特殊字符串的群组
- [LeetCode] Number of Lines To Write String 写字符串需要的行数
- 576. Out of Boundary Paths