Cow Relays 【优先队列优化的BFS】USACO 2001 Open

Cow Relays

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 80 Accepted Submission(s): 13

Description

Farmer John has formed a relay team for a race by choosing K (2 ≤ K ≤ 40) of his cows. The race is run on FJ's farm which has N (4 ≤ N < 800) fields numbered 1..N and M (1 ≤ M ≤ 4000) unique bidirectional pathways that connect pairs of different fields. You will be given the time it takes a cow to traverse each pathway.

The first cow begins the race in field #1 and runs to the finish line in field #N. As soon as the first cow finishes, the next cow then starts from field #1 and runs to field #N and so on. For this race, no two cows can follow precisely the same route (a route is a sequence of fields).

Write a program which computes the minimum possible time required for FJ's relay team. It is guaranteed that some minimum possible time exists. Any cows can revisit a path in her trip to the other barn if that turns out to be required for a "best" solution. As soon as a cow enters field #N, her relay leg is finished.

Input

* Line 1: One line with three integers: K, N, and M

* Lines 2..M+1: Each line contains three integers describing a path: the starting field, the ending field, and the integer time to traverse the path (in the range 1..9500).

Output

One line with a single integer that is the minimum possible time to run a relay.

Sample Input

4 5 8
1 2 1
1 3 2
1 4 2
2 3 2
2 5 3
3 4 3
3 5 4
4 5 6

Sample Output

Hint

Namely: Cow 1: 1->2->5 4
Cow 2: 1->3->5 6
Cow 3: 1->2->1->2->5 6
Cow 4: 1->2->3->5 7

题意概括：

给出一个具有 N 个顶点 M 条边的无向图，求从起点 1 到终点 N 的K条最短路径长度之和；

解题思路：

BFS求最短路，但是顶点可以重复入队，但只允许入队 K 次，因为入队几次就说明了是求到了当前第K的最短路，我们只需要前K个，所以后面的不再入队。

优先队列能保证求到的K条路径一定是最优的。

注意：标记入队次数是在处理该节点时才标记，而不是该节点入队时标记，因为入队不一定被处理，只有被处理了才算用到了该节点来求最短路径。

AC code：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <queue>
 6 #include <vector>
 7 #define INF 0x3f3f3f3f
 8 #define LL long long
 9 using namespace std;
10 int N, M, K, ans;
11 const int MAXN = 900;
12 const int MAXM = 8005;
13 int in_c[MAXN];
14 
15 struct Edge
16 {
17     int v, nxt, w;
18 }edge[MAXM];
19 int head[MAXN], cnt;
20 
21 struct data
22 {
23     int x, len;
24     bool operator<(const data &a) const {
25         return len > a.len;             ///最小值优先
26     }
27 };
28 priority_queue<struct data>que;
29 
30 
31 void init(){
32     memset(head, -1, sizeof(head));
33     memset(in_c, 0, sizeof(in_c));
34     cnt = 0;
35     ans = 0;
36 }
37 
38 void add(int from, int to, int cost)
39 {
40     edge[cnt].v = to;
41     edge[cnt].w = cost;
42     edge[cnt].nxt = head[from];
43     head[from] = cnt++;
44 }
45 
46 void BFS()
47 {
48     //while(!que.empty()) que.pop();
49     struct data it, temp;
50     it.x = 1;
51     it.len = 0;
52     //in_c[1]++;
53     que.push(it);
54     int sum = 0;
55 
56     while(!que.empty()){
57         it = que.top();que.pop();
58         if(it.x == N){
59             sum++;
60             ans+=it.len;
61             if(sum == K) return;
62             continue;
63         }
64         if(++in_c[it.x] > K) continue;
65 
66         for(int i = head[it.x]; i != -1; i = edge[i].nxt){
67             int to = edge[i].v;
68             //printf("to:%d
", to);
69             //if(in_c[to] < K){
70                 //in_c[to]++;
71                 temp.x = to;
72                 temp.len = it.len+edge[i].w;
73                 que.push(temp);
74             //}
75         }
76     }
77 
78 }
79 
80 int main()
81 {
82     int u, v, w;
83     //while(~scanf("%d %d %d", &K, &N, &M)){
84     scanf("%d %d %d", &K, &N, &M);
85         init();
86         for(int i = 1; i <= M; i++){
87             scanf("%d %d %d", &u, &v, &w);
88             add(u, v, w);
89             add(v, u, w);
90         }
91 
92         BFS();
93 
94         printf("%d
", ans);
95     //}
96 
97     return 0;
98 }