比赛 |
9.6 |
评测结果 |
WWTTTTTTTT |
题目名称 |
最小公倍数 |
最终得分 |
0 |
用户昵称 |
123 |
运行时间 |
39.273 s |
代码语言 |
C++ |
内存使用 |
7.97 MiB |
提交时间 |
2024-09-06 21:50:17 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=200010;
int n,m,q,head[N],nxt[N],idx[N],tot=0,vis[N],dp[N];
pair <int,int> val[N],dis[N];
void add(int x,int y,int a,int b)
{
idx[++tot]=y;
nxt[tot]=head[x];
val[tot]=make_pair(b,a);
head[x]=tot;
}
int bfs(int u,int v,int a,int b)
{
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
queue<int> q;
dis[u]=make_pair(1e9,1e9),vis[u]=1;
q.push(u);
while(!q.empty())
{
int t=q.front();q.pop();
for (int i=head[t];i;i=nxt[i])
{
int y=idx[i];
if (vis[y] || min(val[i].first,dis[t].first)<b || min(val[i].second,dis[t].second)<a)
{
continue;
}
q.push(y);
dis[y]=make_pair(min(dis[t].first,val[i].first),min(dis[t].second,val[i].second));
vis[y]=1;
if (y==v) return 1;
}
}
return 0;
}
int main() {
freopen("multiple.in","r",stdin);
freopen("multiple.out","w",stdout);
cin>>n>>m;
while (m--)
{
int x,y,a,b;
scanf("%d%d%d%d",&x,&y,&a,&b);
add(x,y,a,b);
add(y,x,a,b);
}
cin>>q;
while (q--)
{
int v,u,a,b;
scanf("%d%d%d%d",&v,&u,&a,&b);
if (bfs(v,u,a,b))
{
printf("Yes\n");
}
else
{
printf("No\n");
}
}
}