CF1307D 题解

· · 题解

题意

给你一个图，再给你一个集合，让你在集合里连一条边，使得最短路最大（边权为 1）。

思路

我们定义一些前置数组：

定义 dis_i 表示 1 到 i 的最短路径，dis2_i 表示 i 到 n 的最短路径，d_{i,j} 表示 i 到 j 的最短路。

首先，我们知道，如果在集合中连一条边的话，那么 newdis_n \le olddis_n，那么这里以连的两个点为 u, v 举例：

那么此时就可以得出柿子：dis_u + 1 + dis2_v \le dis_n。

同理，如果 dis_u + 1 + dis2_v \le dis_n 的话，那么就有 dis_u + 1 + dis2_v \le dis_v + dis2_v（道理如上）。

柿子 dis_u + 1 + dis2_v \le dis_v + dis2_v 可以化简成 dis_u + 1 \le dis_v。移项后可以得出 dis_v - dis_u \ge 1，所以我们发现 d_{u, v} 要尽可能小才行，所以我们可以按照 dis_i 排序，每次的相邻两个 i 和 i + 1 就一定是可能的最小的 d_{u, v}。

由于最后的答案可能大于 dis_n，所以我们还要跟 dis_n 比较一下。

代码

代码如下：

#include<bits/stdc++.h>
#define int long long    //开 long long

using namespace std;

const int N = 4e5 + 5;

int n, m, k, maxi = 0;
bool vis[N];
int a[N];
int dis[3][N];     //这里是预处理两个 dis 数组

int tot, head[N];

struct Node{
  int to, next;
}edges[N];

void add(int u, int v){
  tot++;
  edges[tot].to = v;
  edges[tot].next = head[u];
  head[u] = tot;
}

void dijkstra(int s, int k){    //dijkstra 模板，其实这里可以用 bfs
  memset(vis, false, sizeof(vis));
  priority_queue<pair<int, int>> q;
    for(int i = 1; i <= n; i++) {
        dis[k][i] = 1e9;
    }
    dis[k][s] = 0;
    q.push(make_pair(dis[k][s], s));
    while(!q.empty()) {
        int x = q.top().second;
        q.pop();
        if(vis[x]) {
            continue;
        }
        vis[x] = true;
        for(int i = head[x]; i; i = edges[i].next) {
            if(1 + dis[k][x] < dis[k][edges[i].to]) {
                dis[k][edges[i].to] = 1 + dis[k][x];
                q.push(make_pair(-dis[k][edges[i].to], edges[i].to));
            }
        }
    }
}

bool cmp(int x, int y){
  return dis[1][x] < dis[1][y];
}

signed main(){
  cin >> n >> m >> k;
  for(int i = 1; i <= k; i++){
    cin >> a[i];
  }
  for(int i = 1; i <= m; i++){
    int u, v;
    cin >> u >> v;
    add(u, v);
    add(v, u);
  }
  dijkstra(1, 1);
  dijkstra(n, 2);
  sort(a + 1, a + 1 + k, cmp);    //按照 dis[i] 排序
  for(int i = 1; i < k; i++){
    maxi = max(maxi, dis[1][a[i]] + dis[2][a[i + 1]] + 1);    //最后计算答案
  }
  maxi = min(maxi, dis[1][n]);    //还要跟 dis[n] 比一比
  cout << maxi << endl;
  return 0;
}