usaco_3_2_6_butter_优先队列+dijkstra.cpp

usaco自己做的1到5章的代码

/*
ID: wangyuc2
PROB:butter
LANG: C++
*/
/*
dijkstra+heap
*/
#include <fstream>
#include <iostream>
#include <string>
#include <memory>
#include <algorithm>
#include <bitset>
#include <queue>
#include <vector>
#define Max 802
#define cin fin
using namespace std;
const int Maxint=99999999;
ifstream fin("butter.in");
ofstream fout("butter.out");
struct Node{
	int Adjvex;
	int val;
};
int dis[Max];
int n,start,cow;
int map[Max][Max];
struct cmp{
	bool operator()(Node a,Node b)
	{
		return a.val>b.val;
	}
};
vector<int> edge[Max];
priority_queue<Node,vector<Node>,cmp> mq;
//queue<int> way;
bool used[Max];
int cows[501];

void init()
{
	int i,m,a,b,l;
	cin>>cow;
//	cout<<"输入定点数，边数和起点："<<endl;
	cin>>n>>m;
	for(i=0;i<cow;i++) cin>>cows[i];
	for(i=0;i<m;i++)
	{
		cin>>a>>b>>l;
		a--;b--;
		map[a][b]=l;
		map[b][a]=l;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}
//	for(i=0;i<n;i++) dis[i]=Maxint;
}

void dijkstra(int start)
{
	int i,j,k;
	Node temp,temp1;
	for(i=0;i<n;i++) dis[i]=Maxint;
	memset(used,false,sizeof(used));
	temp.Adjvex=start;
	temp.val=0;
	dis[temp.Adjvex]=0;
	mq.push(temp);
	while(!mq.empty())
	{
		temp=mq.top();
		mq.pop();
		used[temp.Adjvex]=true;
		//dis[temp.Adjvex]=temp.val;
	//	way.push(temp.Adjvex);
		for(j=0;j<edge[temp.Adjvex].size();j++)
		{
			i=edge[temp.Adjvex][j];
			if(dis[temp.Adjvex]+map[temp.Adjvex][i]<dis[i] && !used[i])
			{
				dis[i]=dis[temp.Adjvex]+map[temp.Adjvex][i];
				temp1.Adjvex=i;
				temp1.val=dis[i];
				mq.push(temp1);
			}
		}
	}
}
int main()
{
	int i,j,k;
	int sum,min=0;
	int ii;
	init();
	for(i=0;i<n;i++) {
		dijkstra(i);
		sum=0;
		for(j=0;j<cow;j++) sum+=dis[cows[j]-1];
//		for(j=0;j<n;j++) cout<<dis[j]<<' ';
		if(sum<min || i==0) min=sum;
	}
	fout<<min<<endl;
//	system("PAUSE");
	return 0;
}