G. Reducing Delivery Cost
给出n<1000个点m<1000条边的无向图
现在只能从m条边中删去一条边
求删去某条边后使得k个点对间的最短路和最短
由于n和m都只有1000 首先想到的就是$Onmlogn$
若考虑某对点的最短路，在删除某条边后会对它们的最短路有什么影响比较困难
应该反过来考虑 先枚举删除某条边再求这对点的最短路就比较容易了
于是Om枚举删除的边 然后对于每条删除边两个端点(设为(u,v) )跑Dijkstra
求得它们到k个点对的最短路
那么删除这条边后对于一个点对(i,j)而言
它们的之间的最短路=min{dis(i,j),dis(i,u)+dis(v,j),dis(i,v)+dis(u,j) }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
#define P pair<ll,ll>
const int Max=1e3+5;
const int Mod=998244353;
const int inf=0x3f3f3f3f;
bool vis[Max],visp[Max][Max];
int n,m,k;
vector<P>mp[Max],Pair;
ll dis[Max][Max];
struct Edge{int u,v;}edge[Max];
void Dijkstra(int start){
for(int i=0;i<=n;i++)vis[i]=0;
priority_queue<P,vector<P>,greater<P> >q;
dis[start][start]=0;
q.push({0,start});
while(!q.empty()){
P temp=q.top();q.pop();
int now=temp.second;
if(vis[now])continue;
vis[now]=1;
for(auto edges:mp[now]){
int cost=edges.second,to=edges.first;
if(dis[start][now]+cost<dis[start][to]){
dis[start][to]=dis[start][now]+cost;
q.push({dis[start][to],to});
}
}
}
}
int main() {
Turnoff;
memset(dis,0x3f,sizeof dis);
cin>>n>>m>>k;int cnt=0;
for(int i=1;i<=m;i++){
int u,v,w;cin>>u>>v>>w;
if(u>v)swap(u,v);
if(visp[u][v])continue;
visp[u][v]=1;
mp[u].push_back({v,w});
mp[v].push_back({u,w});
edge[cnt++]={u,v};
}
for(int i=1;i<=k;i++){
int u,v;cin>>u>>v;
Pair.push_back({u,v});
}
for(int i=1;i<=n;i++)Dijkstra(i);
ll ans=1e18;
for(int i=0;i<cnt;i++){
int cutA=edge[i].u,cutB=edge[i].v;
ll temp=0;
for(auto p:Pair){
int a=p.first,b=p.second;
ll mindis=min(dis[a][cutA]+dis[b][cutB],dis[b][cutA]+dis[a][cutB]);
mindis=min(mindis,dis[a][b]);
temp+=mindis;
}
ans=min(ans,temp);
}
cout<<ans<<endl;
}
|