Silver Cow Party

题目链接POJ-3268



kuangbin带你飞【专题六】 最短路

题目描述

有编号为1-N的牛,它们之间存在一些单向的路径。给定一头牛的编号,其他牛要去拜访它并且拜访完之后要返回自己原来的位置,求这些牛中所花的最长的来回时间是多少。


思路

我们很容易求出从给定点出发,到其他顶点的最短路。那如何求出其他顶点到给定点的最短路呢? 我们可以反向存边,再来计算一次从给定顶点到其他顶点的最短路,两次求出的最短路求和,然后找出最大的那个数值,就是答案!

代码

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
95
96
97
98
99
100
101
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

#define MAX_N 1010
#define MAX_M 100010
#define INF 0x3f3f3f3f

int dist[MAX_N], vis[MAX_N], mat[MAX_N][MAX_N];

struct Min_Heap{
int key, val;
bool operator < (const Min_Heap &a) const
{
return a.val < val;
}
Min_Heap(int tmp_key, int tmp_val)
{
key = tmp_key;
val = tmp_val;
}
};

void init(int n)
{
memset(vis, 0, sizeof(vis));
for(int i = 1; i<=n; i++)
{
for(int j = 1; j<=n; j++)
mat[i][j] = INF;
dist[i] = INF;
}
}

void Union(int x, int y, int val)
{
if(val < mat[x][y])
mat[x][y] = val;
}

void Dijkstra(int n, int v)
{
priority_queue<Min_Heap> S;
dist[v] = 0;
S.push(Min_Heap(v, 0));
while(!S.empty())
{
Min_Heap h = S.top();
S.pop();
int k = h.key, val = h.val;
if(vis[k])
continue;
vis[k] = 1;
for(int i = 1; i<=n; i++)
{
if(!vis[i] && val + mat[k][i] < dist[i])
{
dist[i] = val + mat[k][i];
S.push(Min_Heap(i, dist[i]));
}
}
}
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m, v;
int len[MAX_N];
memset(len, 0, sizeof(len));
cin >> n >> m >> v;
init(n);
for(int i = 1; i<=m; i++)
{
int x, y, val;
cin >> x >> y >> val;
Union(x, y, val);
}
Dijkstra(n, v);//计算每只回去时最少的时间
for(int i = 1; i<=n; i++)
len[i] += dist[i];
for(int i = 1; i<=n; i++)
{
for(int j = 1; j<i; j++)
swap(mat[i][j], mat[j][i]);
}
for(int i = 1; i<=n; i++)
dist[i] = INF;
memset(vis, 0, sizeof(vis));
Dijkstra(n, v);//计算每只来时最少的时间
for(int i = 1; i<=n; i++)
len[i] += dist[i];
int MAX = -INF;
for(int i = 1; i<=n; i++)
MAX = max(MAX, len[i]);
cout << MAX;
return 0;
}
-------------本文结束,感谢您的阅读!-------------