poj 3268 Silver Cow Party dijkstra

缘起

日常浪费生命 poj 3268 Silver Cow Party

分析

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
给出n个点和m条边，接着是m条单向边，代表从牛a到牛b需要花费c时间，现在所有牛要到牛x那里去参加聚会，并且所有牛
参加聚会后还要回来，给你牛x，除了牛x之外的牛，他们都有一个参加聚会并且回来的最短时间，从这些最短时间里找
出一个最大值输出

【输入】
第一行给出 n,m,x 然后m行，每行三个数 a,b,c
1 ≤ N ≤ 1000
1 ≤ M ≤ 100,000
1 ≤ c ≤ 100

【输出】
所有牛中此次聚会最多需要花费的时间

【样例输入】
4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

【样例输出】
10

【限制】
2s

【提示】
Cow 4 proceeds directly to the party (3 units) and returns via farms 1 and 3 (7 
units), for a total of 10 time units.

思路是显然的——边反向建图之后，再跑一次dijkstra即可得到回去最短路.

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
//#include "stdafx.h"

#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
//#define LOCAL
typedef pair<int,int> P; // first是距离, second是顶点标号

int n,m,cnt,x,head[1005], headd[1005],dis[1005],diss[1005];
priority_queue<P, vector<P>, greater<P> > pq; // 小根堆

struct Arc
{
	int from,to,nxt,len;
	Arc(){}
	Arc(int from, int to, int nxt, int len):from(from),to(to),nxt(nxt),len(len){}
}g[100005],gg[100005]; // g是图, gg是反图

void addArc(int a,int b, int c) // 建图&&反向建图
{
	g[cnt] = Arc(a,b,head[a],c);
	head[a] = cnt;
	gg[cnt] = Arc(b,a,headd[b], c);
	headd[b] = cnt;
	cnt++;
}

void dijkstra() // g上跑dijkstra
{
	pq.push(P(0,x));
	while(!pq.empty())
	{
		P top = pq.top();
		pq.pop();
		for (int h = head[top.second]; ~h; h = g[h].nxt)
		{
			int to = g[h].to;
			if (dis[to]>dis[top.second]+g[h].len)
			{
				dis[to] = dis[top.second]+g[h].len;
				pq.push(P(dis[to], to));
			}
		}
	}
}

void dijkstraa() // gg上跑dijkstra（这样写代码丑了点）
{
	pq.push(P(0,x));
	while(!pq.empty())
	{
		P top = pq.top();
		pq.pop();
		for (int h = headd[top.second]; ~h; h = gg[h].nxt)
		{
			int to = gg[h].to;
			if (diss[to]>diss[top.second]+gg[h].len)
			{
				diss[to] = diss[top.second]+gg[h].len;
				pq.push(P(diss[to], to));
			}
		}
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	memset(dis, 0x3f, sizeof(dis));
	memset(diss, 0x3f, sizeof(diss));
	memset(head, -1, sizeof(head));
	memset(headd, -1, sizeof(headd));
	scanf("%d%d%d", &n, &m, &x);
	dis[x] = diss[x] = 0;
	int a,b,c;
	while(m--)
	{
		scanf("%d%d%d", &a, &b, &c);
		addArc(a,b,c);
	} // 建图&&反向建图
	dijkstra();
	dijkstraa();
	int ans = 0;
	for (int i = 1; i<=n; i++)
	{
		ans = max(ans, dis[i]+diss[i]); // dis[i]是1到i的最短路（即回来的最短路），diss[i]是i到1的最短路（即去的最短路）
	}
	printf("%d\n",ans);
	return 0;
}

ac情况

Status Accepted
Time 16ms
Memory 360kB
Length 1824
Lang C++
Submitted 2019-08-30 15:43:57
Shared
RemoteRunId 20818992

.

上述代码如果有不懂，参考【1】

参考

【1】https://yfsyfs.github.io/2019/08/22/hdu-2544-dijkstra%E6%A8%A1%E6%9D%BF/