【求助】第18个点WA了,有孤点处理
查看原帖
【求助】第18个点WA了,有孤点处理
121479
聪明的猪楼主2020/10/20 19:09

RT,请问这是什么duliu数据

#include <cstdio>
#include <cstring>

#include <vector>
#include <queue>

using namespace std;

struct Node {
  int key, dis;
  bool operator <(const Node& a) const {
    return dis > a.dis;
  }

  Node() {}

  Node(int a, int b) {
    key = a;
    dis = b;
  }
};

vector<int> kGraph[100005];
int kOddDis[100005];
int kEvenDis[100005];
bool kIsVisOdd[100005];
bool kIsVisEven[100005];
priority_queue<Node> kQueue;

void Dijkstra(void);

int main(void) {
  int m(0), n(0), q(0);
  memset(kOddDis, 0x3f, sizeof(kOddDis));
  memset(kEvenDis, 0x3f, sizeof(kEvenDis));
  memset(kIsVisOdd, false, sizeof(kIsVisOdd));
  memset(kIsVisEven, false, sizeof(kIsVisEven));

  scanf("%d %d %d", &n, &m, &q);

  for (int i = 0; i < m; ++i) {
    int u(0), v(0);
    scanf("%d %d", &u, &v);
    kGraph[u].push_back(v);
    kGraph[v].push_back(u);
  }

  Dijkstra();

  for (int i = 0; i < q; ++i) {
    int a(0), l_stage(0);
    scanf("%d %d", &a, &l_stage);

    if (l_stage % 2 == 0)
      puts(kEvenDis[a] < l_stage + 1 ? "Yes" : "No");
    else
      puts(kOddDis[a] < l_stage + 1 ? "Yes" : "No");
  }

  return 0;
}

void Dijkstra(void) {
  Node now_node;

  for (auto iter = kGraph[1].begin(); iter != kGraph[1].end(); ++iter) {
    kQueue.push(Node(*iter, 1));
    kOddDis[*iter] = 1;
  }

  while (!kQueue.empty()) {
    now_node = kQueue.top();
    kQueue.pop();

    for (auto iter = kGraph[now_node.key].begin();
         iter != kGraph[now_node.key].end(); ++iter) {
      int new_node(*iter);

      if (kEvenDis[new_node] > kOddDis[now_node.key] + 1) {
        kEvenDis[new_node] = kOddDis[now_node.key] + 1;
        if (!kIsVisEven[new_node]) {
          kIsVisEven[new_node] = true;
          kQueue.push(Node(new_node, kEvenDis[new_node]));
        }
      }

      if (kOddDis[new_node] > kEvenDis[now_node.key] + 1) {
        kOddDis[new_node] = kEvenDis[now_node.key] + 1;
        if (!kIsVisOdd[new_node]) {
          kIsVisOdd[new_node] = true;
          kQueue.push(Node(new_node, kOddDis[new_node]));
        }
      }
    }
  }
}
2020/10/20 19:09
加载中...