Silver Cow Party
One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1..N is going to attend the big cow party to be held at farm #X (1 ≤ X ≤ N). A total of M (1 ≤ M ≤ 100,000) unidirectional (one-way roads connects pairs of farms; road i requires Ti (1 ≤ Ti ≤ 100) units of time to traverse. Each cow must walk to the party and, when the party is over, return to her farm. Each cow is lazy and thus picks an optimal route with the shortest time. A cow's return route might be different from her original route to the party since roads are one-way. Of all the cows, what is the longest amount of time a cow must spend walking to the party and back?
Input
Line 1: Three space-separated integers, respectively: N, M, and X
Lines 2..M+1: Line i+1 describes road i with three space-separated integers: Ai, Bi, and Ti. The described road runs from farm Ai to farm Bi, requiring Ti time units to traverse.
Output
Line 1: One integer: the maximum of time any one cow must walk.
Sample Input
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
Sample Output
10
Hint
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.
Source
题目类型：单源最短路(SPFA)
算法分析：构建邻接表和逆邻接表，分别计算从x点到其他各个点的最短路径(使用邻接表)，然后计算从各个点到x点的最短路径(使用逆邻接表)。然后对于每个点累加起两次距离，求最后累加之后的距离中最大的即可。注意求该问题使用其他算法时间复杂度可能会偏高
|
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 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 |
#include <iostream> #include <fstream> #include <algorithm> #include <iomanip> #include <cstring> #include <cstdio> #include <cmath> #include <map> #include <string> #include <vector> #include <stack> #include <queue> #include <set> #include <list> #include <ctime> using namespace std; const int maxn = 3600; const int INF = 66666666; struct Node { int v, w; Node (int vv, int ww) : v (vv), w (ww) {} Node () {} }; int ans[maxn], dis[maxn]; bool inq[maxn]; int n, m, x; vector <Node> edge[maxn], redge[maxn]; void spfa (int dir) { int i; for (i = 1; i <= n; i++) dis[i] = INF; memset (inq, false, sizeof (inq)); dis[x] = 0; inq[x] = true; queue <int> q; q.push (x); if (dir == 0) { while (!q.empty ()) { int temp = q.front (); q.pop (); inq[temp] = false; int i; for (i = 0; i < edge[temp].size (); i++) { if (dis[edge[temp][i].v] > dis[temp] + edge[temp][i].w) { dis[edge[temp][i].v] = dis[temp] + edge[temp][i].w; if (!inq[edge[temp][i].v]) { q.push (edge[temp][i].v); inq[edge[temp][i].v] = true; } } } } } else { while (!q.empty ()) { int temp = q.front (); q.pop (); inq[temp] = false; int i; for (i = 0; i < redge[temp].size (); i++) { if (dis[redge[temp][i].v] > dis[temp] + redge[temp][i].w) { dis[redge[temp][i].v] = dis[temp] + redge[temp][i].w; if (!inq[redge[temp][i].v]) { q.push (redge[temp][i].v); inq[redge[temp][i].v] = true; } } } } } } int main() { // ifstream cin ("aaa.txt"); while (cin >> n >> m >> x) { int i; for (i = 0; i < maxn; i++) { edge[i].clear (); redge[i].clear (); } int val_a, val_b, val_w; for (i = 0; i < m; i++) { cin >> val_a >> val_b >> val_w; edge[val_a].push_back (Node (val_b, val_w)); redge[val_b].push_back (Node (val_a, val_w)); } spfa (0); memset (ans, 0, sizeof (ans)); for (i = 1; i <= n; i++) { if (i == x) continue; ans[i] += dis[i]; } spfa (1); int maxval = -INF; for (i = 1; i <= n; i++) { if (i == x) continue; ans[i] += dis[i]; if (ans[i] > maxval) maxval = ans[i]; } cout << maxval << endl; } return 0; } |
使用链式前向星实现
|
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 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define i64 long long const int INF = 0x7FFFFFFF - 6; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1000 + 66; struct Node { int v, w, next; }; Node edge[maxn*maxn]; int head[maxn], edgelen; Node redge[maxn*maxn]; int rhead[maxn], redgelen; void Init () { memset (head, -1, sizeof (head)); memset (edge, -1, sizeof (edge)); memset (rhead, -1, sizeof (rhead)); memset (redge, -1, sizeof (redge)); edgelen = 0; redgelen = 0; } void AddEdge (int u, int v, int w) { edge[edgelen].v = v; edge[edgelen].w = w; edge[edgelen].next = head[u]; head[u] = edgelen++; redge[redgelen].v = u; redge[redgelen].w = w; redge[redgelen].next = rhead[v]; rhead[v] = redgelen++; } //分别表示节点到源点的最距离和顶点个数 int dis[maxn], inq[maxn], rdis[maxn], rinq[maxn]; int n, m, x; //数组下标从1开始 void spfa (int s) { for (int i = 1; i <= n; i++) { dis[i] = INF; inq[i] = 0; } dis[s] = 0; queue <int> qu; qu.push (s); inq[s]++; while (!qu.empty ()) { int tt = qu.front(); qu.pop (); inq[tt]--; int pa = head[tt]; while (pa != -1) { int pb = edge[pa].v; if (dis[tt] < INF && dis[pb] > dis[tt] + edge[pa].w) { dis[pb] = dis[tt] + edge[pa].w; if (!inq[pb]) { qu.push (pb); inq[pb]++; } } pa = edge[pa].next; } } } void rspfa (int s) { for (int i = 1; i <= n; i++) { rdis[i] = INF; rinq[i] = 0; } rdis[s] = 0; queue <int> qu; qu.push (s); rinq[s]++; while (!qu.empty ()) { int tt = qu.front(); qu.pop (); rinq[tt]--; int pa = rhead[tt]; while (pa != -1) { int pb = redge[pa].v; if (rdis[tt] < INF && rdis[pb] > rdis[tt] + redge[pa].w) { rdis[pb] = rdis[tt] + redge[pa].w; if (!rinq[pb]) { qu.push (pb); rinq[pb]++; } } pa = redge[pa].next; } } } int main() { // CPPFF; // CFF; while (scanf ("%d%d%d", &n, &m, &x) != EOF) { Init (); int u, v, w; for (int i = 1; i <= m; i++) { scanf ("%d%d%d", &u, &v, &w); AddEdge (u, v, w); } spfa (x); rspfa (x); int maxval = 0; for (int i = 1; i <= n; i++) if (dis[i] < INF && rdis[i] < INF && i != x) maxval = max (maxval, dis[i] + rdis[i]); printf ("%d\n", maxval); } return 0; } |
- « 上一篇：poj3264
- poj3320：下一篇 »