[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; } ```