USACO Training Section 3.2 Sweet Butter

英文原题  中文题译

大意：农场之间有路构成稀疏无向图，若干奶牛分散在不同农场，要让奶牛到某个农场集合，如何代价最小。

稀疏图上求到所有点对的最短路径，用Bellman Ford算法的队列实现(SPFA)，其思想是：开始时队列中只有源节点，不断取出队列中的首节点，并对其相邻节点检查是否可用该节点更新其距离，若可，且相邻节点不在队中，则将其入队。这和宽度优先搜索很像，所不同的是每个节点可以多次入队。

在求得最短路径之后计算集合的代价取最小值即可。

/*
ID: blackco3
TASK: butter
LANG: C++
*/
#include <iostream>
#include <memory.h>
using namespace std;
#define _max_farm_ 800
#define _max_path_ 1450
#define _max_cow_ 500

struct t_path {
	int v1, v2, dis ;
} pathes[_max_path_];
struct t_adj {
	int to, dis ;
	t_adj( int t=0, int d=0 ) : to(t), dis(d) {} ;
} adj_buf[_max_path_<<1] ;
struct t_farm {
	int n_adj ;
	t_adj *adj ;
} farms[_max_farm_];
int cows[_max_cow_], n_cow, n_farm, n_path; 

int sdis[_max_farm_], queue[_max_farm_], in_que[_max_farm_] ;
void Bellman_Ford_SPFA( int source ){
	memset( sdis, 0x7f, sizeof(int)*n_farm );
	memset( in_que, 0, sizeof(int)*n_farm ) ;
	int *head=queue, *tail=queue; 
	sdis[source]=0 , in_que[source]=1, *(tail++)=source ;
	do{
		register int cfarm= *head ;
		in_que[cfarm]=0, head = (head-queue)==_max_farm_-1 ? queue : head+1;
		for( t_adj *p_adj=farms[cfarm].adj; p_adj!=farms[cfarm].adj+farms[cfarm].n_adj; p_adj++ ){
			if( p_adj->dis + sdis[cfarm] >= sdis[p_adj->to] )
				continue ;
			sdis[p_adj->to] = p_adj->dis + sdis[cfarm] ;
			if( !in_que[p_adj->to] ){
				*tail=p_adj->to , in_que[p_adj->to]=1 ;
				tail = (tail-queue)==_max_farm_-1 ? queue : tail+1;
			}
		}
	}while( head!=tail );
}


int main() {
	freopen("butter.in", "r", stdin);
	freopen("butter.out", "w", stdout);
	cin >> n_cow >> n_farm >> n_path ;
	for( int i=0; i<n_cow; i++ )
		cin >> cows[i], cows[i]-- ;
	memset( farms, 0, sizeof(t_farm)*n_farm ) ;
	for( t_path *pc=pathes; pc!=pathes+n_path; pc++ ){
		cin >> pc->v1 >> pc->v2 >> pc->dis ;
		farms[--pc->v1].n_adj++, farms[--pc->v2].n_adj++ ;
	}
	t_adj *p_adj=adj_buf;
	for( int i=0; i<n_farm; i++ )
		farms[i].adj=p_adj, p_adj+=farms[i].n_adj, farms[i].n_adj=0 ;
	for( t_path *pc=pathes; pc!=pathes+n_path; pc++ ){
		int v1=pc->v1, v2=pc->v2, dis=pc->dis ;
		farms[v1].adj[ farms[v1].n_adj++ ]=t_adj(v2,dis);
		farms[v2].adj[ farms[v2].n_adj++ ]=t_adj(v1,dis);
	}
	int min_total=0x7fffffff ;
	for( int i=0; i<n_farm; i++ ){
		Bellman_Ford_SPFA(i);
		int total=0 ;
		for( int j=0; j<n_cow; j++ )
			total += sdis[ cows[j] ] ;
		min_total = min_total>total ? total : min_total ;
	}
	cout << min_total << endl ;
	return 0;
}