洛谷 P1821 [USACO07FEB]银牛派对Silver Cow Party

银牛派对

正向建图+反向建图， 两边跑dijkstra，然后将结果相加即可。

反向建图以及双向建图的做法是学习图论的必备思想。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std;

//Mystery_Sky

//

#define maxn 1000010

#define maxm 5000050

#define INF 0x3f3f3f3f

struct Edge{

	int next;

	int w;

	int to;

}edge1[maxn];

Edge edge2[maxn];

int n, m, X;

int head1[maxn], head2[maxn], cnt1, cnt2;

int vis1[maxn], vis2[maxn], dis1[maxn], dis2[maxn];

inline void add_edge1(int u, int v, int w)

{

	edge1[++cnt1].to = v;

	edge1[cnt1].next = head1[u];

	edge1[cnt1].w = w;

	head1[u] = cnt1;

}

inline void add_edge2(int u, int v, int w)

{

	edge2[++cnt2].to = v;

	edge2[cnt2].next = head2[u];

	edge2[cnt2].w = w;

	head2[u] = cnt2;

}

struct node{

	int dis;

	int pos;

	inline bool operator <(const node &x) const

	{

		return x.dis < dis;

	}

};

priority_queue <node> q1;

priority_queue <node> q2;

inline void dijkstra1()

{

	dis1[X] = 0;

	q1.push((node) {0, X});

	while(!q1.empty()) {

		node top = q1.top();

		q1.pop();

		int x = top.pos;

		if(vis1[x]) continue;

		vis1[x] = 1;

		for(int i = head1[x]; i; i = edge1[i].next) {

			int y = edge1[i].to;

			if(dis1[y] > dis1[x] + edge1[i].w) {

				dis1[y] = dis1[x] + edge1[i].w;

				if(!vis1[y]) q1.push((node) {dis1[y], y});

			}

		}

	}

}

inline void dijkstra2()

{

	dis2[X] = 0;

	q2.push((node) {0, X});

	while(!q2.empty()) {

		node top = q2.top();

		q2.pop();

		int x = top.pos;

		if(vis2[x]) continue;

		vis2[x] = 1;

		for(int i = head2[x]; i; i = edge2[i].next) {

			int y = edge2[i].to;

			if(dis2[y] > dis2[x] + edge2[i].w) {

				dis2[y] = dis2[x] + edge2[i].w;

				if(!vis2[y]) q2.push((node) {dis2[y], y});

			}

		}

	}

}

int ans = 0;

int main() {

	scanf("%d%d%d", &n, &m, &X);

	int u, v, w;

	memset(dis1, INF, sizeof(dis1));

	memset(dis2, INF, sizeof(dis2));

	for(int i = 1; i <= m; i++) {

		scanf("%d%d%d", &u, &v, &w);

		add_edge1(u, v, w);

		add_edge2(v, u, w);

	}

	dijkstra1();

	dijkstra2();

	for(int i = 1; i <= n; i++) {

		if(i == X) continue;

		if(ans < dis1[i] + dis2[i]) ans = dis1[i] + dis2[i];

	}

	printf("%d\n", ans);

	return 0;

}