【最短路】POJ 3268 Silver Cow Party

POJ 3268 Silver Cow Party

题意：给一个有向图及终点x，求各点与x之间往返最短路之和的最大值

思路：floyd当然是最吼的……但点太多，T了。于是反向建边，这样就可以通过求x的dij两次得到各点往x的最短路和从x返回各点的最短路。代码写得过于繁琐了。

struct node {
	LL d;
	int u;
	bool operator < (const node& k) const {
		return d > k.d;
	}
};

struct Edge {
	int from, to;
	LL dis;
	Edge(int u,int v,LL d):from(u),to(v),dis(d){}
};

int n, m,x;
int p[maxn];
vector<Edge> Edges;
vector<Edge> A_Edges;
vector<int> G[maxn];
vector<int> A_G[maxn];

bool done[maxn];
LL d[maxn];
LL A_d[maxn];

void dij(int start,int A) {
	memset(done, false, sizeof(done));
	for (int i = 1; i <= n; i++) {
		if (A == 0) d[i] = (i == start ? 0 : INF);
		else A_d[i] = (i == start ? 0 : INF);
	}
	priority_queue<node> Q;
	Q.push(node{ 0, start });
	while (!Q.empty()) {
		node x = Q.top(); Q.pop();
		int u = x.u;
		if (done[u]) continue;
		if (A == 0) {
			for (int i = 0; i < G[u].size(); i++) {
				Edge& e = Edges[G[u][i]];
				if (d[u] + e.dis < d[e.to]) {
					d[e.to] = d[u] + e.dis;
					Q.push(node{ d[e.to],e.to });
				}
			}
			done[u] = true;
		}
		else {
			for (int i = 0; i < A_G[u].size(); i++) {
				Edge& e = A_Edges[A_G[u][i]];
				if (A_d[u] + e.dis < A_d[e.to]) {
					A_d[e.to] = A_d[u] + e.dis;
					Q.push(node{ A_d[e.to],e.to });
				}
			}
			done[u] = true;
		}
	}

}

void solve(){
	cin >> n >> m >> x;
	Edges.clear();
	for (int i = 0; i <= n; i++) G[i].clear();

	Edges.push_back(Edge(0, 0, 0));
	A_Edges.push_back(Edge(0, 0, 0));

	int num = 0;

	for (int i = 1; i <= m; i++) {
		int u, v;
		LL d;
		cin >> u >> v >> d;
		Edges.push_back(Edge(u, v, d));
		G[u].push_back(++num);
		A_Edges.push_back(Edge(v, u, d));
        //反向建边
		A_G[v].push_back(num);
	}
	
	dij(x,0);
	dij(x,1);

	LL ans_len = -1;
	for (int i = 1; i <= n; i++) {
		LL distance = d[i]+A_d[i];
		if (distance >= INF) continue;
		ans_len = max(ans_len, distance);
	}
	cout << ans_len;
}

【最短路】POJ 3268 Silver Cow Party

原文：https://www.cnblogs.com/streamazure/p/12932656.html