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：

 #include <cstdio>

 #include <iostream>

 #include <cstring>

 #include <algorithm>

 #include <queue>

 #include <vector>

 #define INF 0x3f3f3f3f

 #define LL long long

 using namespace std;

 int N, M, K, ans;

 const int MAXN = ;

 const int MAXM = ;

 int in_c[MAXN];

 struct Edge

 {

     int v, nxt, w;

 }edge[MAXM];

 int head[MAXN], cnt;

 struct data

 {

     int x, len;

     bool operator<(const data &a) const {

         return len > a.len;             ///最小值优先

     }

 };

 priority_queue<struct data>que;

 void init(){

     memset(head, -, sizeof(head));

     memset(in_c, , sizeof(in_c));

     cnt = ;

     ans = ;

 }

 void add(int from, int to, int cost)

 {

     edge[cnt].v = to;

     edge[cnt].w = cost;

     edge[cnt].nxt = head[from];

     head[from] = cnt++;

 }

 void BFS()

 {

     //while(!que.empty()) que.pop();

     struct data it, temp;

     it.x = ;

     it.len = ;

     //in_c[1]++;

     que.push(it);

     int sum = ;

     while(!que.empty()){

         it = que.top();que.pop();

         if(it.x == N){

             sum++;

             ans+=it.len;

             if(sum == K) return;

             continue;

         }

         if(++in_c[it.x] > K) continue;

         for(int i = head[it.x]; i != -; i = edge[i].nxt){

             int to = edge[i].v;

             //printf("to:%d\n", to);

             //if(in_c[to] < K){

                 //in_c[to]++;

                 temp.x = to;

                 temp.len = it.len+edge[i].w;

                 que.push(temp);

             //}

         }

     }

 }

 int main()

 {

     int u, v, w;

     //while(~scanf("%d %d %d", &K, &N, &M)){

     scanf("%d %d %d", &K, &N, &M);

         init();

         for(int i = ; i <= M; i++){

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

             add(u, v, w);

             add(v, u, w);

         }

         BFS();

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

     //}

     return ;

 }

巴特西

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

Cow Relays

最新文章

热门文章