題目鏈接：點擊查看

題目大意：給出一個由 n 個點和 m 條邊組成的無向圖，其中有 k 個點被標記了，題目要求選出兩個被標記的點，連接一條邊，使得從點 1 到點 n 的最短路最大

題目分析：讀完題后，大部分同學應該都會在腦中浮現出一個 n * n 的做法吧，那就是先用bfs求出 dis[ i ][ 0 ] 和 dis[ i ][ 1 ] ，分別表示從點 1 到點 i 的距離和從點 n 到點 i 的距離，然后兩層循環枚舉被標記的點，計算出 dis[ i ][ 0 ] + dis[ j ][ 1 ] + 1 的最大值就是答案了，思路確實沒有問題，現在的問題是如何優化

先來考慮一個比較簡單的事情，假如現在有兩個點 i 和 j ，如果其建邊的話，最短路可能是 1 -> i -> j -> n 或者 1 -> j -> i -> n，這樣代表的距離也就是 dis[ i ][ 0 ] + dis[ j ][ 1 ] + 1 和 dis[ i ][ 1 ] + dis[ j ][ 0 ] + 1 了，因為題目要求的是最短路，所以很顯然會選擇更小的那一個，換句話說，當滿足 dis[ i ][ 0 ] + dis[ j ][ 1 ] + 1 < dis[ i ][ 1 ] + dis[ j ][ 0 ] + 1 時，我們會選擇前者，通過移項以及約分，不難化簡到：dis[ i ][ 0 ] - dis[ i ][ 1 ]?< dis[ j ][ 0 ] - dis[ j ][ 1 ]，這個公式又代表什么呢？也就是說，當我們現在有兩個被標記的點時，dis[ i ][ 0 ] - dis[ i ][ 1 ] 更小的這個點會放在前面，而另外一個點會放在后面

得出這個結論后，我們就可以先對 k 個點按照 dis[ i ][ 0 ] - dis[ i ][ 1 ] 從小到大的順序排序，因為我們需要維護 dis[ i ][ 0 ] + dis[ j ][ 1 ] + 1 的最大值，我們暫且規定點 i 在點 j 的前面，也就是如果點 i 和點 j 建邊的話，一定滿足最短路是 1 -> i -> j -> n 的，這樣我們O(n)枚舉一遍位于后面的點 j ，然后找到點 j 前面的 dis[ i ][ 0 ] 的最大值，也就是前綴的最大值，這樣可以保證相加之和是最大的，最后記得特判一下上限就好了，上限是原圖的最短路

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;vector<int>node[N];int id[N],dis[N][2];void bfs(int st,int pos) {queue<int>q;q.push(st);dis[st][pos]=0;while(q.size()){int u=q.front();q.pop();for(auto v:node[u])if(dis[v][pos]>dis[u][pos]+1){dis[v][pos]=dis[u][pos]+1;q.push(v);}} }bool cmp(int a,int b) {return dis[a][0]-dis[a][1]<dis[b][0]-dis[b][1]; }int main() { //#ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); //#endif // ios::sync_with_stdio(false);memset(dis,inf,sizeof(dis));int n,m,k;scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=k;i++)scanf("%d",id+i);while(m--){int u,v;scanf("%d%d",&u,&v);node[u].push_back(v);node[v].push_back(u);}bfs(1,0);bfs(n,1);sort(id+1,id+1+k,cmp);int ans=0,mmax=dis[id[1]][0];for(int i=2;i<=k;i++){ans=max(ans,mmax+dis[id[i]][1]+1);mmax=max(mmax,dis[id[i]][0]);}printf("%d\n",min(dis[n][0],ans));return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 1307D Cow and Fields(最短路+思维)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。