60分搜索求助orz,大佬们帮忙看看qwq
查看原帖
60分搜索求助orz,大佬们帮忙看看qwq
1107382
Yg2023楼主2024/4/3 17:31
#include <iostream>
//#include <stdio.h>
#include <math.h>
#include <cmath>
#include <string.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <fstream>
#include <string>
//#include <map>
//#include <unordered_map>
#define rd read()
#define il inline
#define ll long long
#define int long long
using namespace std;
const int L = 5e6 + 10;
int head[L], edge[L], nxt[L], now = 0, ck[L >> 1], vis[L >> 1];
int a[50];
il int read(){
    int res = 0, f = 1;
    char c = getchar();
    while(c < '0' || c >'9')
    {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
    {
        res = res * 10 + c - 48;
        c = getchar();
    }
    return res * f;
}
il void addEdge(int u, int v)
{
    edge[++now] = v;
    nxt[now] = head[u];
    head[u] = now;
}
queue<int> q;
il bool bfs(int st, int ed)
{
    while(!q.empty()) q.pop();
    memset(vis, 0, sizeof(vis));
    vis[st] = 1;
    q.push(st);
    while(!q.empty())
    {
        int pos = q.front(); q.pop();
        for(int i = head[pos]; i; i = nxt[i])
        {
            int j = edge[i];
            if(j == ed) return true;
            if(vis[j] || ck[j]) continue;
            q.push(j); vis[j] = 1;
        }
    }
    return false;
}
signed main(){
    int n, m, k, q;
    cin >> n >> m >> k >> q;
    int u, v, t;
    for(int i = 0; i < m; ++i)
    {
        u = rd; v = rd;
        //cin >> u >> v;
        addEdge(u, v); addEdge(v, u);
    }
    for(int i = 0; i < q; ++i)
    {
        for(int j = 0; j < k; ++j)
        {
            t = rd;
            //cin >> t;
            a[j] = t;
            ck[t] = 1;
        }
        //printf("out\n");
        bool ok = 1;
        for(int j = 1; j < k; ++j)
        {
            if(!bfs(a[j - 1], a[j]))
            {
                //cout << a[j - 1] << ' ' << a[j] << endl;
                ok = 0; break;
            }
            ck[a[j - 1]] = ck[a[j]] = 0;
        }
        if(ok) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

就是题目要求一个点(传感器)只在第一次的时候返回,我好像处理了这种情况qwq(返回过就把标记消除了)

不知道为什么还是错的qwq 大佬们可以帮忙看看嘛,感谢

2024/4/3 17:31
加载中...