简单题意：给n个点m条边无向图，每次询问两个点之间是否有长度为d的路径（不一定是简单路径）。即可以重复走一条边。
思路：
蛮水的叭。我们知道路径可以重复走，所以只要找到一条和d奇偶性相同的最短路，就可以做到了。
因为可以在一条边上不停来来回回，也就是在最短路上加上了一个偶数-->偶数大小任意！！！；
此处应有代码：
1 #include<bits/stdc++.h>
2 using namespace std;
3 int head[5005],tot;
4 struct pp
5 {
6 int to,nxt;
7 }e[10005];
8 int q[5005];
9 int dis[5005][2];
10 bool used[5009];
11 int n,m,k;
12 struct lpp
13 {
14 int x,y,c,num,ans;
15 }lq[1000009];
16 void add(int x,int y)
17 {
18 e[++tot].to=y;
19 e[tot].nxt=head[x];
20 head[x]=tot;
21 }
22 bool cmp(lpp a,lpp b)
23 {
24 return a.x<b.x;
25 }
26 bool cmp1(lpp a,lpp b)
27 {
28 return a.num<b.num;
29 }
30 void SPFA(int s)
31 {
32 memset(dis,0,sizeof(dis));
33 memset(used,-1,sizeof(used));
34 int h=1,t=1;
35 for(int i=head[s];i!=-1;i=e[i].nxt)
36 {
37 used[e[i].to]=1;
38 dis[e[i].to][1]=1;
39 q[t++]=e[i].to;
40 }
41 while(h!=t)
42 {
43 int x=q[h++];
44 h%=5003;
45 used[x]=0;
46 for(int i=head[x];i!=-1;i=e[i].nxt)
47 {
48 int v=e[i].to;
49 if(dis[x][0]&&!dis[v][1])
50 {
51 dis[v][1]=dis[x][0]+1;
52 if(!used[v]) used[v]=1,q[t++]=v,t%=5003;
53 }
54 if(dis[x][1]&&!dis[v][0])
55 {
56 dis[v][0]=dis[x][1]+1;
57 if(!used[v]) used[v]=1,q[t++]=v,t%=5003;
58 }
59
60 }
61
62 }
63 }
64
65 int main()
66 {
67 memset(head,-1,sizeof(head));
68 tot=0;
69 scanf("%d%d%d",&n,&m,&k);
70 int x,y;
71 for(int i=1;i<=m;i++)
72 {
73 scanf("%d%d",&x,&y);
74 add(x,y);
75 add(y,x);
76 }
77 for(int i=1;i<=k;i++)
78 {scanf("%d%d%d",&lq[i].x,&lq[i].y,&lq[i].c);lq[i].num=i;}
79 sort(lq+1,lq+k+1,cmp);
80 int j=1;
81 for(int i=1;i<=n;i++)
82 {
83 SPFA(i);
84 while(lq[j].x==i)
85 {
86 if(dis[lq[j].y][lq[j].c%2]&&dis[lq[j].y][lq[j].c%2]<=lq[j].c)
87 lq[j].ans=1;
88 j++;
89 }
90 }
91 sort(lq+1,lq+k+1,cmp1);
92 for(int i=1;i<=k;i++)
93 {
94 if(lq[i].ans) printf("TAK\n");
95 else printf("NIE\n");
96 }
97 return 0;
98 }
View Code