題目鏈接：點擊查看

題目大意：給出一個由 n 個點和 m 條邊組成的無向無權圖，再給出一個含有 m 個正整數的權值表記為數組 val ，現在需要從點 a 走到點 b 然后在走到點 c ，問如何分配 val 里的權值到圖中的每條邊上，可以使得最短路最小，輸出這個最小值

題目分析：因為是要求最短路，所以先用迪杰斯特拉處理出分別以點 a 、點 b 、點 c 為起點的最短路，記為 dis_a , dis_b , dis_c ，最初的想法是枚舉每條邊：

如果這條邊在 a -> b 的最短路上，且在 b -> c 的最短路上，那么 cnt1++

如果這條邊在 a -> b 的最短路上，或在 b -> c 的最短路上，那么 cnt2++

對 val 數組排序后并維護前綴和 sum ，那么答案顯然就是 sum[ cnt1 + cnt2 ] + sum[ cnt1 ] 了

但是這個思路有個致命的錯誤，那就是無法處理有多條最短路的情況

重新梳理思路，稍微分類討論一下，因為我們要走 a -> b 和 b -> c 的最短路，無非有兩種情況：

a -> b 和 b -> c 的最短路沒有交集

a -> b 和 b -> c 的最短路存在交集

如果沒有交集的話，那么直接計算 a -> b 和 b -> c 的邊數之和 cnt ，sum[ cnt ] 就是答案了

如果存在交集的話，那么只能是像樣例 1 那樣，存在一個 x ，使得路線為?a -> x -> b -> x -> c ，這樣 O( n ) 枚舉點 x ，然后 O( 1 ) 維護最小值就行了

現在的問題是，如何判斷 a -> b 和 b -> c 是否存在交集呢？其實不用想那么復雜，當 x == b 時，最短路就變成了 a -> b -> b -> b -> c 了，也就是 a -> b -> c ，此時的情況 2 就退化為了情況 1 ，所以每次都默認 a -> b 和 b -> c 都存在交集就好了

至于如何 O( 1 ) 維護答案，因為我們已經知道了交集的部分是 x -> b 這個部分，而初始的圖我們默認權值都是 1 ，那么跑出來的最短路實際上也就是邊的個數，換句話說，dis( a , b ) 的意義從 a -> b 的最短路，變成了 a -> b 最少多少條邊可以到達，這樣我們只需要計算出 dis( a , x ) + dis( b , x ) + dis( c , x ) 就能知道一共需要多少條邊了，因為 x -> b 這里重復走了一次，所以額外加上前 dis( b , x ) 條邊的權值和就是答案了?

代碼：
?

#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;struct Edge {int to,w,next; }edge[N<<1];int head[N],a[N],b[N],c[N],cnt,n,m;//鏈式前向星 LL val[N];bool vis[N];void addedge(int u,int v,int w) {edge[cnt].to=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt++; }struct Node {int to,w;Node(int TO,int W){to=TO;w=W;}bool operator<(const Node& a)const{return w>a.w;} };void Dijkstra(int st,int d[]) {priority_queue<Node>q;for(int i=1;i<=n;i++){vis[i]=false;d[i]=inf;}d[st]=0;q.push(Node(st,0));while(q.size()){Node cur=q.top();int u=cur.to;q.pop();if(vis[u])continue;vis[u]=true;for(int i=head[u];i!=-1;i=edge[i].next)//掃描出所有邊 {int v=edge[i].to;int w=edge[i].w;if(d[v]>d[u]+w)//更新 {d[v]=d[u]+w;q.push(Node(v,d[v]));}}} }void init() {for(int i=1;i<=n;i++)head[i]=-1;cnt=0; }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){int A,B,C;scanf("%d%d%d%d%d",&n,&m,&A,&B,&C);init();for(int i=1;i<=m;i++)scanf("%lld",val+i);sort(val+1,val+1+m);for(int i=1;i<=m;i++){val[i]+=val[i-1];int u,v;scanf("%d%d",&u,&v);addedge(u,v,1);addedge(v,u,1);}Dijkstra(A,a),Dijkstra(B,b),Dijkstra(C,c);LL ans=0x3f3f3f3f3f3f3f3f;for(int i=1;i<=n;i++){if(a[i]+b[i]+c[i]>m)continue;ans=min(ans,val[b[i]]+val[a[i]+b[i]+c[i]]);}printf("%lld\n",ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 1343E Weights Distributing(最短路)的全部內容，希望文章能夠幫你解決所遇到的問題。

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