CF1888E Time Travel 题解

FFTotoro · 2023-10-23 21:11:20 · 题解

这题可以使用经过改动的最短路 Dijkstra 算法。

建图的时候把时间标记也打上。考虑怎么进行这个 Dijkstra 算法：假设走到点 u，当前的最短时间为 d_u，枚举所有出边连接的点 i，如果 i 的时间标记有在 d_u 之后出现（假设最早的那个是 x），那么就可以更新 d_i\leftarrow\min\{d_i,x\}。这个可以将每个标记存一下在 a 数组中出现的所有位置，需要查找的时候 upper_bound 即可。

笔者在考场上 k 写成 n 吃了一发罚，警钟撅烂。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,t; cin>>n>>t;
  vector<vector<pii> > g(n);
  for(int i=1;i<=t;i++){
    int m; cin>>m;
    while(m--){
      int u,v; cin>>u>>v;
      g[--u].emplace_back(i,--v);
      g[v].emplace_back(i,u);
    }
  } // 建图
  int k; cin>>k;
  vector<vector<int> > a(t+1);
  for(int i=1;i<=k;i++){
    int x; cin>>x;
    a[x].emplace_back(i);
  } // 存位置
  vector<int> d(n,1e7); d[0]=0;
  vector<bool> b(n);
  priority_queue<pii,vector<pii>,greater<pii> > q;
  q.emplace(0,0);
  while(!q.empty()){
    int u=q.top().second; q.pop();
    if(b[u])continue; b[u]=true;
    for(auto [w,i]:g[u]){
      auto l=upper_bound(a[w].begin(),a[w].end(),d[u]);
      if(l!=a[w].end()&&*l<d[i])q.emplace(d[i]=*l,i);
    }
  } // Dijkstra 过程
  cout<<(d[n-1]==1e7?-1:d[n-1])<<endl;
  return 0;
}