[题解]CF1433G-Reducing Delivery Cost

Posted on In

[CF1433G]Reducing Delivery Cost

题意

给出一张无向带权图\(G\)和\(k\)个点对, 你可以将最多一条边的权值变为0, 求\(k\)个点对之间最短路之和的最小值

图中存在重边和自环.

\(1 \leq n \leq 1000, 1 \leq m \leq \frac{n(n-1)}{2},1 \leq k \leq 1000\)

题解

套路题, 一开始想麻烦了.

设\(D[i][j]\)为\((i,j)\)间的最短路. 对于每条边\((f,t)\)有两种情况:

  1. 无论该边权值是否为零, 都不在点对\((x,y)\)的最短路上. 删掉该边后答案仍为\(D[x][y]\).
  2. 删掉该边前/后该边位于点对\((x,y)\)的最短路上. 删掉该边后答案为\(\min(D[x][f]+D[t][y],D[x][t]+D[f][y])\)

我们跑\(n\)遍Dijkstra预处理出任意点对最短路,再对于每条边枚举\(k\)个点对即可求出答案.总复杂度\(O(nm\log n + km)\)

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
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int INF = 1e9+10;
const int maxn = 1e3+10;
const int maxm = maxn*maxn;
typedef pair<int,int> Node;
int head[maxn],vis[maxn],dis[maxn];
int D[maxn][maxn]; 
int viscnt[maxm];
struct Edge{
	int f,t,w,next;
	Edge(int f = 0,int t = 0,int w = 0,int next = 0):f(f),t(t),w(w),next(next){}
}edge[maxm];
int cnt = 0,n,m;
void addedge(int f,int t,int w){
	edge[cnt] = Edge(f,t,w,head[f]);
	head[f] = cnt++;
}
void dijkstra(int s){
	for(int i = 0;i <= n;i++){
		dis[i] = INF;
		vis[i] = 0;
	}
	dis[s] = 0;
	priority_queue<Node,vector<Node>,greater<Node> >pq;
	pq.push({dis[s],s});
	while(!pq.empty()){
		int u = pq.top().second;
		pq.pop();
		if(vis[u])continue;
		vis[u] = 1;
		for(int i = head[u];~i;i = edge[i].next){
			int v = edge[i].t,w = edge[i].w;
			if(dis[v] > dis[u] + w){
				dis[v] = dis[u] + w;
				if(!vis[v]){
					pq.push({dis[v],v});
				}
			}
		}
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	memset(head,-1,sizeof(head));
	memset(D,0x3f3f3f3f,sizeof(D));
	int k;
	cin >> n >> m >> k;
	for(int i = 1;i <= m;i++){
		int f,t,w;
		cin >> f >> t >> w;
		addedge(f,t,w);
		addedge(t,f,w);
	}
	for(int i = 1;i <= n;i++){
		dijkstra(i);
		for(int j = 1;j <= n;j++)D[i][j] = D[j][i] = dis[j];
	}
	vector<Node>path; 
	for(int i = 1;i <= k;i++){
		int x,y;
		cin >> x >> y;
		path.push_back({x,y});
	} 
	ll ans = LLONG_MAX;
	for(int i = 0;i < cnt;i++){
		int f = edge[i].f,t = edge[i].t;
		ll tans = 0;
		for(int j = 0;j < k;j++){
			int x = path[j].first,y = path[j].second;
			tans += min({D[x][y],D[x][f]+D[t][y],D[x][t]+D[f][y]});
		}
		ans = min(ans,tans);	
	}
	cout << ans << endl;
}