蒟蒻求条
查看原帖
蒟蒻求条
1070026
yuhong056楼主2025/7/19 16:24
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 2e5 + 25, MOD = 1e4 + 7, INF = 1e9 + 7;

int n, t, k;
int a[MAXN];
vector<pair<int, int> >te[MAXN];
map<int, vector<int> >e[MAXN];

int dis[MAXN];

struct Node{
  int t, u;
  bool operator < (const Node &oth) const {
    return !(t < oth.t);
  }
};

priority_queue<Node>s;

void Record(Node d) {
  if(d.t < dis[d.u]) {
    dis[d.u] = d.t;
    s.push(d);
  }
}

void dijk() {
  for(int i = 1; i <= n; i++) {
    dis[i] = INF;
  }
  Record({1, 1});
  while(s.size()) {
    auto u = s.top();
    s.pop();
    for(auto [v, s] : e[u.u]) {
      int pos = lower_bound(s.begin(), s.end(), u.t) - s.begin();
      if(pos < s.size())Record({s[pos], v});
    }
  }
}

int main(){
  cin >> n >> t;
  for(int i = 1, m; i <= t; i++) {
    cin >> m;
    for(int u, v, j = 1; j <= m; j++) {
      cin >> u >> v;
      te[i].push_back({u, v});
    }
  }
  cin >> k;
  for(int i = 1; i <= k; i++) {
    cin >> a[i];
    for(auto [u, v] : te[a[i]]) {
      e[u][v].push_back(i);
      e[v][u].push_back(i);
    }
  }
  dijk();
  cout << (dis[n] > k ? -1 : dis[n]);
  return 0;
}

没法过样例

2025/7/19 16:24
加载中...