傳送門
文章目錄
題意：
n≤2e5,m≤2e5n\le2e5,m\le2e5n≤2e5,m≤2e5
思路：
怎么感覺每場div3div3div3都有一個巧妙的圖論題。
首先如果只有兩個點的話，肯定是一次bfsbfsbfs之后取前disdisdis小的www作為邊權即可。
但是這個有三個點，如果兩條路徑沒有重疊的話，那么答案根據我們上面說的一樣，不過跑兩次bfsbfsbfs即可。但是路徑是有可能重疊的，多畫幾個圖就可發現，重疊的部分一定是從bbb出發到aaa的最短路上的一段，記這一段的終點為ddd，那么答案路徑一定是a?>d?>b?>d?>ca->d->b->d->ca?>d?>b?>d?>c，那么分別從a,b,ca,b,ca,b,c為起點做一遍bfsbfsbfs，讓后枚舉ddd，對于重疊的部分取最小的權值，讓后非重疊部分從未取的部分從小到大依次取即可。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#include<random>
#include<cassert>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].l+tr[u].r)>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=1000010,mod
=1e9+7,INF
=0x3f3f3f3f;
const LL inf
=0x3f3f3f3f3f3f3f3f;
const double eps
=1e-6;int n
,m
,a
,b
,c
;
LL w
[N
];
int dis
[3][N
];
vector
<int>v
[N
];
void bfs(int st
,int flag
) {for(int i
=1;i
<=n
;i
++) dis
[flag
][i
]=INF
;queue
<int>q
; q
.push(st
);dis
[flag
][st
]=0;while(q
.size()) {int u
=q
.front(); q
.pop();for(auto x
:v
[u
]) {if(dis
[flag
][x
]>dis
[flag
][u
]+1) {dis
[flag
][x
]=dis
[flag
][u
]+1;q
.push(x
);}}}
}int main()
{
int _
; scanf("%d",&_
);while(_
--) {scanf("%d%d%d%d%d",&n
,&m
,&a
,&b
,&c
);for(int i
=1;i
<=m
;i
++) scanf("%lld",&w
[i
]);sort(w
+1,w
+1+m
);for(int i
=1;i
<=m
;i
++) w
[i
]=w
[i
-1]+w
[i
];for(int i
=1;i
<=n
;i
++) v
[i
].clear();for(int i
=1;i
<=m
;i
++) {int a
,b
; scanf("%d%d",&a
,&b
);v
[a
].pb(b
); v
[b
].pb(a
);}LL ans
=inf
;bfs(a
,0); bfs(b
,1); bfs(c
,2);for(int i
=1;i
<=n
;i
++) {if(dis
[0][i
]+dis
[2][i
]+dis
[1][i
]>m
) continue;LL now
=w
[dis
[1][i
]]*2+w
[dis
[0][i
]+dis
[2][i
]+dis
[1][i
]]-w
[dis
[1][i
]];ans
=min(ans
,now
);}printf("%lld\n",ans
);}return 0;
}
總結
以上是生活随笔為你收集整理的Codeforces Round #636 (Div. 3) E. Weights Distributing 思维 + bfs的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
