acdrem1083 人民城管爱人民 DP

思路：d(i, 0)表示从节点i到达大运村的最短路径，d(i, 1)表示从节点i到达大运村的次短路径。

1.最短路：当做DAG处理即可。

2.次短路：假设当前在u点处，下一个节点是v。v到终点的最短路是d(v, 0)，次短路是d(v, 1)，u到v的距离是w(u, v)，只能封锁一条路，即只能删除一条边。分成两种情况：

a.将封锁用在了v点到达终点的路上，则此时GG拥有主动权，可以选择最小的路径，即Imin = min(w(u, v) + d(v, 1))，;

b.将封锁用在u-v这条路径上面，则此时城管拥有主动权，可以封锁最短路径，则GG这能选择次短路径Hmin。

则d(u, 1) = max(Imin, Hmin)

AC代码

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <utility>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define eps 1e-10
#define inf 0x3f3f3f3f
#define PI pair<int, int>
typedef long long LL;
const int maxn = 10000 + 5;
int n, m;
int d[maxn][2], in[maxn], Top[maxn], c[maxn*20];

struct Edge{
	int from, to, dist, nex;
	Edge() {}
	Edge(int u, int v, int d, int ne):from(u), to(v), dist(d), nex(ne){}
}edge[maxn*20];

int edgenum, head[maxn];
void add_edge(int u, int v, int dis) {
	edge[edgenum] = Edge(u, v, dis, head[u]);
	head[u] = edgenum++;
}

void topsort() { //逆向拓扑序
	queue<int>q;
	for(int i = 0; i < n; ++i) if(!in[i]) q.push(i);
	int num = 0;
	while(!q.empty()) {
		int u = q.front(); q.pop();
		for(int i = head[u]; i != -1; i = edge[i].nex) if(i&1){
			int v = edge[i].to;
			--in[v];
			if(!in[v]) q.push(v);
		}
		Top[num++] = u;
	}
}

void solve(int u) {
	if(u == n-1) {d[u][0] = d[u][1] = 0; return;} //终点
	int num = 0, Imin = inf;
	for(int i = head[u]; i != -1; i = edge[i].nex) if(!(i&1)){
		int v = edge[i].to;
		//最短路
		d[u][0] = min(d[u][0], d[v][0] + edge[i].dist);
		//次短路
		Imin = min(Imin, d[v][1] + edge[i].dist); // GG掌握主动权
		c[num++] = d[v][0] + edge[i].dist; //城管有主动权
	}
	if(num < 2) {d[u][1] = inf; return;} //GG无法到达从u到达终点
	int fir = c[0], sec = c[1]; //最小和次小
	if(fir > sec) swap(fir, sec);
	for(int i = 2; i < num; ++i) {
		if(c[i] <= fir) {
			sec = fir;
			fir = c[i];
		}
		else sec = min(sec, c[i]);
	}
	d[u][1] = max(Imin, sec);
	if(d[u][1] > inf) d[u][1] = inf;
	if(d[u][0] > inf) d[u][0] = inf;
}

int main() {
	int T;
	scanf("%d", &T);
	while(T--) {
		edgenum = 0;
		memset(head, -1, sizeof(head));
		memset(d, inf, sizeof(d));
		memset(in, 0, sizeof(in));
		scanf("%d%d", &n, &m);
		int u, v, dis;
		for(int i = 0; i < m; ++i) {
			scanf("%d%d%d", &u, &v, &dis);
			add_edge(u, v, dis);
			add_edge(v, u, dis);
			in[u]++;
		}
		topsort();
		for(int i = 0; i < n; ++i) {
			solve(Top[i]);
		}
		if(d[0][1] >= inf) printf("-1\n");
		else printf("%d\n", d[0][1]);
	}
	return 0;
}

如有不当之处欢迎指出！

巴特西

acdrem1083 人民城管爱人民 DP

最新文章

热门文章