work.cpp work.in work.out
题目描述
凯凯的工厂正在有条不紊地生产一种神奇的零件，神奇的零件的生产过程自然也很神奇。工厂里有 n 位工人，工人们从 1∼n 编号。某些工人之间存在双向的零件传送带。保证每两名工人之间最多只存在一条传送带。
如果 x 号工人想生产一个被加工到第 L(L>1) 阶段的零件，则所有与 x 号工人有传送带直接相连的工人，都需要生产一个被加工到第 L−1 阶段的零件（但 x 号工人自己无需生产第 L−1 阶段的零件）。
如果 x 号工人想生产一个被加工到第 1 阶段的零件，则所有与 x 号工人有传送带直接相连的工人，都需要为 x 号工人提供一个原材料。
轩轩是 1 号工人。现在给出 q 张工单，第 i 张工单表示编号为 ai 的工人想生产一个第 Li 阶段的零件。轩轩想知道对于每张工单，他是否需要给别人提供原材料。他知道聪明的你一定可以帮他计算出来！
输入格式
第一行三个正整数 n，m 和 q，分别表示工人的数目、传送带的数目和工单的数目。
接下来 m 行，每行两个正整数 u 和 v，表示编号为 u 和 v 的工人之间存在一条零件传输带。保证 u≠v 。
接下来 q 行，每行两个正整数 a 和 L，表示编号为 a 的工人想生产一个第 L 阶段的零件。
输出格式
共 q 行，每行一个字符串“Yes”或者“No”。如果按照第 i 张工单生产，需要编号为 1 的轩轩提供原材料，则在第 i 行输出“Yes”；否则在第 i 行输出“No”。注意输出不含引号。
样例输入
3 2 6
1 2
2 3
1 1
2 1
3 1
1 2
2 2
3 2样例输出
No
Yes
No
Yes
No
Yes
问题提示
【输入输出样例1说明】
编号为 1 的工人想生产第 1 阶段的零件，需要编号为 2 的工人提供原材料。
编号为 2 的工人想生产第 1 阶段的零件，需要编号为 1 和 3 的工人提供原材料。
编号为 3 的工人想生产第 1 阶段的零件，需要编号为 2 的工人提供原材料。
编号为 1 的工人想生产第 2 阶段的零件，需要编号为 2 的工人生产第 1 阶段的零 件，需要编号为 1 和 3 的工人提供原材料。
编号为 2 的工人想生产第 2 阶段的零件，需要编号为 1 和 3 的工人生产第 1 阶段的零件，他/她们都需要编号为 2 的工人提供原材料。
编号为 3 的工人想生产第 2 阶段的零件，需要编号为 2 的工人生产第 1 阶段的零件，需要编号为 1 和 3 的工人提供原材料。
【输入输出样例2说明】
编号为 1 的工人想生产第 1 阶段的零件，需要编号为 2 和 5 的工人提供原材料。
编号为 1 的工人想生产第 2 阶段的零件，需要编号为 2 和 5 的工人生产第 1 阶段的零件，需要编号为 1,3,4 的工人提供原材料。
编号为 1 的工人想生产第 3 阶段的零件，需要编号为 2 和 5 的工人生产第 2 阶段的零件，需要编号为 1,3,4 的工人生产第 1 阶段的零件，需要编号为 2,3,4,5 的工人提供原材料。
编号为 1 的工人想生产第 4 阶段的零件，需要编号为 2 和 5 的工人生产第 3 阶段的零件，需要编号为 1,3,4 的工人生产第 2 阶段的零件，需要编号为 2,3,4,5 的工人生产第 1 阶段的零件，需要全部工人提供原材料。
编号为 1 的工人想生产第 5 阶段的零件，需要编号为 2 和 5 的工人生产第 4 阶段的零件，需要编号为 1,3,4 的工人生产第 3 阶段的零件，需要编号为 2,3,4,5 的工人生产第 2 阶段的零件，需要全部工人生产第 1 阶段的零件，需要全部工人提供原材料。
【数据规模与约定】
共20个测试点。
1≤u,v,a≤n。
测试点 1~4：1≤n,m≤1000，q=3，L=1 。
测试点 5~8：1≤n,m≤1000，q=3，1≤L≤10 。
测试点 9~12：1≤n,m,L≤1000，1≤q≤100 。
测试点 13~16：1≤n,m,L≤1000，1≤q≤105 。
测试点 17~20：1≤n,m,q≤105，1≤L≤109 。
正文
我们需要先思考几个点
1.工人的数量 n, 从1~n开始编号
2.图 ， 无权无向图（工人-节点 传送带 - 边）
3.L - 零件的阶段 ，x 当前的节点
4.从邻接点提供上一阶段的零件，原材料为起点
5.轩轩 1号
6.q工单的总数
ou[x]送轩轩为起点到达x的最小偶数步。l>=ou[x]ji[x]送轩轩为起点到达x的最小奇数步。l>=ji[x]
struct node{
int state,s;//状态 最短路
};
int ans[N];// 当前状态对应的最短路
void bfs(){
queue<node> q; //处理起点
vis[s]=1;
q.push(node{s,0});
while(!q,empty()){
node cur=q.front();
q.pop();
ans[cur.state]=cur.s;
for(){
if(nxt)
{//相邻状态是否可到达
vis[nxt]=1;
q.push(node{nxt,cur.s+1});
}
}
}
}
ans[xxx];ou[x] = min(ji[相邻点]+1)ji[x] = min(ou[相邻点]+1)
· 邻接矩阵· 邻接表
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,q;
int ji[N],ou[N];
vector<int> g[N];
void bfs()
{
memset(ji,0x3f,sizeof(ji));
memset(ou,0x3f,sizeof(ou));
queue<int> s;
s.push(1);
ou[1]=0;
while(!s.empty())
{
int u=s.front();
s.pop();
for(int i=0;i<(int)g[u].size();i++){
int v=g[u][i];
if(ou[v] > ji[u]+1){
ou[v]=ji[u]+1;
s.push(v);
}
if(ji[v]>ou[u]+1)
{
ji[v]=ou[u]+1;
s.push(v);
}
}
}
}
int main()
{
//freopen("work.in","r",stdin);
//freopen("work.out","w",stdout);
int u,v;
cin>>n>>m>>q;
for(int i=1;i<=m;i++)
{
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
bfs();
int a,l;
while(q--)
{
cin>>a>>l;
if((l%2!=0 && ji[a]<=l) || (l%2==0 && ou[a]<=l)){
cout<<"Yes"<<'\n';
}
else{
cout<<"No"<<'\n';
}
}
return 0;
}非常简单~
AC~
网址：P5663 [CSP-J2019] 加工零件 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
https://www.luogu.com.cn/problem/P5663