題目:

?

?

?

---

樣例解釋：

樣例#1：
?

編號為 1 的工人想生產(chǎn)第 1 階段的零件，需要編號為 2 的工人提供原材料。
編號為 2 的工人想生產(chǎn)第 1 階段的零件，需要編號為 1 和 3 的工人提供原材料。
編號為 3 的工人想生產(chǎn)第 1 階段的零件，需要編號為 2 的工人提供原材料。
編號為 1 的工人想生產(chǎn)第 2 階段的零件，需要編號為 2 的工人生產(chǎn)第 1 階段的零件，需要為編號 1 和 3 的工人提供原材料。
編號為 2 的工人想生產(chǎn)第 2 階段的零件，需要編號為 1 和 3 的工人生產(chǎn)第 1 階段的零件，他/她們都需要編號為 2 的工人提供原材料。
編號為 3 的工人想生產(chǎn)第 2 階段的零件，需要編號為 2 的工人生產(chǎn)第 1 階段的零件，需要編號為 1 和 3 的工人提供原材料。
樣例#2：
?

編號為 1 的工人想生產(chǎn)第 1 階段的零件，需要編號為 2 和 5 的工人提供原材料。
編號為 1 的工人想生產(chǎn)第 2 階段的零件，需要編號為 2 和 5 的工人生產(chǎn)第 1 階段的零件，需要編號為 1,3,4 的工人提供原材料。
編號為 1 的工人想生產(chǎn)第 3 階段的零件，需要編號為 2 和 5 的工人生產(chǎn)第 2 階段的零件，需要編號為 1,3,4 的工人生產(chǎn)第 1 階段的零件，需要編號為 2,3,4,5 的工人提供原材料。
編號為 1 的工人想生產(chǎn)第 4 階段的零件，需要編號為 2 和 5 的工人生產(chǎn)第 3 階段的零件，需要編號為 1,3,4 的工人生產(chǎn)第 2 階段的零件，需要編號為 2,3,4,5 的工人生產(chǎn)第 1 階段的零件，需要全部工人提供原材料。
編號為 1 的工人想生產(chǎn)第 5 階段的零件，需要編號為 2 和 5 的工人生產(chǎn)第 4 階段的零件，需要編號為 1,3,4 的工人生產(chǎn)第 3 階段的零件，需要編號為 2,3,4,5 的工人生產(chǎn) 第 2 階段的零件，需要全部工人生產(chǎn)第 1 階段的零件，需要全部工人提供原材料。?

---

代碼1：（40-60分算法?）

思路：

設(shè)求第3點為第3階段時，點1是否需要提供原材料。

【3,3】 => 【2,2】，【4,2】

【2,2】 => 【1,1】，【3,1】
【4,2】 => 【3,1】，【5,1】

【1,1】 => 【2,0】，【5,0】
【3,1】 => 【2,0】，【4,0】
【5,1】 => 【1,0】，【4,0】 # 此處1需要提供原材料

比較容易想到對于每個詢問進(jìn)行暴搜，若點1為0，則Yes
時間復(fù)雜度很高，必然超時。

#include <bits/stdc++.h>
using namespace std;const int MAXN=1005;
int vex[MAXN],k,n,m,q;
struct edge {int u,v,next;
}e[MAXN*2];int vis[MAXN][MAXN];void add(int u,int v){k++;e[k].u=u;e[k].v=v;e[k].next=vex[u];vex[u]=k;
}void dfs(int u,int s){if(s==-1||vis[u][s]) return;vis[u][s]=1;for(int i=vex[u];i;i=e[i].next){int v=e[i].v;dfs(v,s-1);}return;
}int main(){cin>>n>>m>>q;while(m--){int u,v;cin>>u>>v;add(u,v);add(v,u);}while(q--){int u,L;memset(vis,0,sizeof(vis));cin>>u>>L;dfs(u,L);if(vis[1][0]) cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
}

---

代碼2：（滿分算法）

思路：

觀察發(fā)現(xiàn)，由于1->2的路徑長度為1，只要點2的階段為奇數(shù)，則點1一定要提供原材料（1->2->1->2->...)

觀察發(fā)現(xiàn)，由于1->2->3的路徑長度為2，只要點3的階段為偶數(shù)，則點1一定要提供原材料

從1到v，路徑很多，長度不盡相同。如果1到v的路徑長度存在4時，v在階段4、6、8、10…時，1肯定可以為0。當(dāng)v的路徑長度存在3時，v在3、5、7、9…階段，1肯定可以為0。

因此要求的就是1到v的最短奇數(shù)路徑和最短偶數(shù)路徑。

若v的階段為偶數(shù)x，存在v的最短偶數(shù)路徑y(tǒng)，滿足x>=y，1即可為0。

若v的階段為奇數(shù)x，存在v的最短奇數(shù)路徑y(tǒng)，滿足x>=y，1即可為0。

設(shè)dis[v][0]為1到v的最短偶數(shù)路徑，設(shè)dis[v][1]為1到v的最短奇數(shù)路徑，

則有：

dis[v][0] = min(dis[v][0],dis[u][1]+1)
dis[v][1] = min(dis[v][1],dis[u][0]+1)

對于初始點1，dis[1][0]顯然等于0，dis[1][1]顯然不可能，設(shè)為無窮大。

代碼：

#include <bits/stdc++.h>
using namespace std;const int MAXN=1e5+5;
int vex[MAXN],k,n,m,q;
struct edge {int u,v,next;
} e[MAXN*2];int vis[MAXN][2],dis[MAXN][2],que[MAXN*10],q2[MAXN*10],head,rear;void add(int u,int v) {k++;e[k].u=u;e[k].v=v;e[k].next=vex[u];vex[u]=k;
}void SPFA() {for(int i=1; i<=n; i++) dis[i][0]=dis[i][1]=1e9;dis[1][0]=0;head=1;rear=0;que[++rear]=1;while(head<=rear) {int u=que[head];int t=q2[head];head++;vis[u][t]=0;for(int i=vex[u]; i; i=e[i].next) {int v=e[i].v;if(dis[v][0]>dis[u][1]+1) {dis[v][0]=dis[u][1]+1;if(!vis[v][0]) {vis[v][0]=1;que[++rear]=v;q2[rear]=0;}}if(dis[v][1]>dis[u][0]+1) {dis[v][1]=dis[u][0]+1;if(!vis[v][1]) {vis[v][1]=1;que[++rear]=v;q2[rear]=1;}}}}return;
}int main() {freopen("work.in","r",stdin);freopen("work.out","w",stdout);cin>>n>>m>>q;while(m--) {int u,v;cin>>u>>v;add(u,v);add(v,u);}SPFA();if(vex[1]==0) dis[1][0]=1e9; //補(bǔ)丁，若1點沒有連接邊，則1的偶數(shù)路徑?jīng)]有。while(q--) {int u,L;cin>>u>>L;if(L>=dis[u][L%2]) cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
}

?

?

?