---
# System prepended metadata

title: '[CODEFORCES 1307D Cow and Fields](https://codeforces.com/contest/1307/problem/D)'

---

[CODEFORCES 1307D Cow and Fields](https://codeforces.com/contest/1307/problem/D)
=

## 題目大意
給連通圖，有 $n$ 個點 $m$ 條雙向邊
沒有重邊，沒有自環，點從 $1$ 到 $n$ 編號
這些點中有 $k$ 個特殊點，要**只挑兩點**加入一條雙向邊，使圖最短路徑從 $1$ 到 $n$ 盡量長
> 意思是若是加 $(a, b)$ 邊後算出的最短路比加 $(b, c)$ 邊後還要短
> 那麼要選 $(b, c)$ 邊

==若特殊點與特殊點間原本有邊，還是能加邊==

## 輸入
$n, m, k$
$k$ 個特殊點 $a_1, a_2, \cdots , a_k$
$m$ 對點 (邊)

## 輸出
最短路徑長度

## 解法 1
明顯的，在加入一條邊之後或多或少會讓最短路更短
- 如果更短了，肯定是最短路徑用了新加的這條邊
- 如果沒有改善，那就是最短路徑沒有改走新加的邊

也就是說，只需關心**當最短路徑用了新加的邊**的狀況
那麼設此邊為 $(a, b)$ 則要讓 $1 \rightsquigarrow n$ 盡量長，
而路徑是 $1 \rightsquigarrow a \to b \rightsquigarrow n$ 或 $1 \rightsquigarrow b \to a \rightsquigarrow n$
> 這裡 $x \rightsquigarrow y$ 是 $x$ 到 $y$ 的最短路徑

設 $d_x(y)$ 為 $x \rightsquigarrow y$ 的長度
> 則 $1 \rightsquigarrow a \to b \rightsquigarrow n$ 的長度就是 $d_1(a) + 1 + d_n(b)$

若最短路徑是 $1 \rightsquigarrow a \to b \rightsquigarrow n$
則長度會有 $d_1(a) + 1 + d_n(b) \le d_1(b) + 1 + d_n(a)$

而任意特殊點對(邊) $(a, b)$ 都得滿足此不等式，也就是例如有點對 $(a, b), (b, c), (c, a)$
會有三個不等式要滿足，假設為
$d_1(a) + 1 + d_n(b) < d_1(b) + 1 + d_n(a)$
$d_1(b) + 1 + d_n(c) < d_1(c) + 1 + d_n(b)$
$d_1(c) + 1 + d_n(a) < d_1(a) + 1 + d_n(c)$
> 在特殊點為三個以上，就不會出現等於關係了

會發現這些不等式能化簡成
$d_1(a) - d_n(a) < d_1(b) - d_n(b)$
$d_1(b) - d_n(b) < d_1(c) - d_n(c)$
$d_1(c) - d_n(c) < d_1(a) - d_n(a)$
再化簡
$\underline{d_1(a) - d_n(a)} < d_1(b) - d_n(b) < d_1(c) - d_n(c) < \underline{d_1(a) - d_n(a)}$
會發現得得到矛盾的結論

所以須從確定的結論往前推，不失一般性的，設有
$d_1(a) - d_n(a) < d_1(b) - d_n(b) < d_1(c) - d_n(c)$
則回推的不等式為
$d_1(a) + 1 + d_n(b) < d_1(b) + 1 + d_n(a)$
$d_1(b) + 1 + d_n(c) < d_1(c) + 1 + d_n(b)$
$d_1(a) + 1 + d_n(c) < d_1(c) + 1 + d_n(a)$
所以要比較這三者的大小 $d_1(a) + 1 + d_n(b), d_1(b) + 1 + d_n(c), d_1(a) + 1 + d_n(c)$

推廣至一般狀況，若是 $d_1(a_1)-d_n(a_1) < d_1(a_2)-d_n(a_2) < \cdots < d_1(a_k)-d_n(a_k)$
則需要比較所有 $d_1(a_x) + 1 + d_n(a_y)$ 其中 $1 \le x < y \le k$

```cpp
#include<bits/stdc++.h>
using namespace std;

int const maxn = 2e5 + 10;

int n, m, k, x, y;
vector<int> E[maxn], a;

void bfs(int s, vector<int> &d) {
  queue<int> q;
  set<int> vis;
  q.push(s);
  vis.insert(s);
  d[s] = 0;
  while(q.size()) {
    int u = q.front(); q.pop();
    for(int v: E[u]) {
      if(vis.count(v)) continue;
      vis.insert(v);
      d[v] = d[u] + 1;
      q.push(v);
    }
  }
}

int main()
{
  scanf("%d%d%d", &n, &m, &k);

  a.resize(k);
  for(int i = 0; i < k; i++) scanf("%d", &a[i]);
  for(int i = 0; i < m; i++) {
    scanf("%d%d", &x, &y);
    E[x].push_back(y);
    E[y].push_back(x);
  }

  vector<int> d1(n+1), dn(n+1);
  bfs(1, d1);
  bfs(n, dn);

  sort(a.begin(), a.end(), [&](int x, int y) { return d1[x]-dn[x] < d1[y]-dn[y]; });

  int ans = 0, d1_mx = 0;
  for(int i = 0; i+1 < k; i++) {
    d1_mx = max(d1_mx, d1[a[i]]);
    ans = max(ans, d1_mx + 1 + dn[a[i+1]]);
  }

  printf("%d\n", min(ans, d1[n]));

  return 0;
}
```

## 解法 2
同樣只關心有加入新邊的情況

設特殊點 $a, b$ 滿足 $d_1(a) < d_1(b)$ 有雙向邊 $(a, b)$，則有三種情況需考慮﹔
- $d_1(n) < d_1(a) < d_1(b)$
最短路徑不經過 $a, b$
- $d_1(a) < d_1(n) < d_1(b)$
最短路徑不經過 $b$
- $d_1(a) < d_1(b) < d_1(n)$
$d_1(a) + 1 < d_1(b) + 1$，且 $d_n(b)$ 與 $d_n(a)$ 只相差 $1$
若是 $x \in \{a, b\}. d_1(x) + d_n(x) > d_1(n)$，則最短路徑不經過 $x$。

由上推得 $d_1(a) + 1 + d_n(b) \le d_1(b) + 1 + d_n(a)$
所以特殊點依照 BFS 的深度排列，比較所有 $d_1(a_x) + 1 + d_n(a_y)$ 其中 $1 \le x < y \le k$ 得解


```cpp
#include<bits/stdc++.h>
using namespace std;

int const maxn = 2e5 + 10;

int n, m, k, a, x, y;
vector<int> E[maxn], ord; // ord := order
vector<bool> sp; // sp := special

void bfs(int s, vector<int> &d) {
  queue<int> q;
  q.push(s);
  d.assign(n+1, -1);
  d[s] = 0;

  while(q.size()) {
    int u = q.front(); q.pop();
    if(s == 1 && sp[u]) ord.push_back(u);

    for(int v: E[u]) {
      if(d[v] != -1) continue;
      d[v] = d[u] + 1;
      q.push(v);
    }
  }
}

int main()
{
  scanf("%d%d%d", &n, &m, &k);

  sp.assign(n+1, false);
  for(int i = 0; i < k; i++) scanf("%d", &a), sp[a] = true;
  for(int i = 0; i < m; i++) {
    scanf("%d%d", &x, &y);
    E[x].push_back(y);
    E[y].push_back(x);
  }

  vector<int> d1, dn;
  bfs(1, d1);
  bfs(n, dn);

  int ans = 0, d1_mx = 0;
  for(int i = 0; i+1 < ord.size(); i++) {
    d1_mx = max(d1_mx, d1[ord[i]]);
    ans = max(ans, d1_mx + 1 + dn[ord[i+1]]);
  }

  printf("%d\n", min(ans, d1[n]));

  return 0;
}
```