2449.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"stdio.h"
#include"list"
#include"queue"
using namespace std;

const int size=1000;
typedef int type;

struct edge
{
	int to;
	type v;
};

list<edge> e[size];

////////////////////////////////////////////////////////////////////////////////////////////////
//	dijstra		连通返回1，否则返回0；
//	strat		源点；
//	e		邻接表；
//	ans		返回到各点的最短距离；

bool dijstra_list(int start,int n,list<edge> e[size],type ans[size])
{
	const type max=99999999;

	int i,j,k;
	list<edge>::iterator iter;
	type dis[size],temp;
	bool reach[size];

	for(i=0;i<n;i++)
		reach[i]=false,dis[i]=max;

	dis[start]=0;

	for(i=0;i<n;i++)
	{
		k=-1;
		for(j=0;j<n;j++)
		{
			if(	!reach[j]	//dijstra 
				&&(k<0||dis[k]>dis[j]))
				k=j;
		}

		if(k<0)break;

		reach[k] = true;

		for(iter=e[k].begin() ; iter!=e[k].end() ; iter++)
		{
			temp=dis[k]+iter->v;
			if(temp<dis[iter->to])
				dis[iter->to]=temp;	
		}
	}

	for(j=0;j<n;j++)
		ans[j]=dis[j];
	
	return k>=0;
}

///////////////////////////////////////////////////////////////////////////////////////


int dis[1000],start,end,kth,n,m;
list<edge> pri[size];

struct cmp
{
	bool operator()(edge a,edge b)const
	{
		return dis[a.to]+a.v>dis[b.to]+b.v;
	}
};

void init()
{
	int a,b,v,i;
	edge eg;
	scanf("%d %d",&n,&m);

	for(i=0;i<n;i++)
		e[i].clear();

	for(i=0;i<m;i++)
	{
		scanf("%d %d %d",&a,&b,&v);
		eg.to=b-1;
		eg.v=v;
		e[a-1].push_back(eg);
		eg.to=a-1;
		pri[b-1].push_back(eg);
	}
	scanf("%d %d %d",&start,&end,&kth);
	
	start--,end--;

	dijstra_list(start,n,e,dis);
}	
	
priority_queue<edge,vector<edge>,cmp> pri_q;

int Astar()
{
	int i,j;bool key;
	edge nd,ndt;
	nd.to=end;
	nd.v=0;
		
	pri_q.push(nd);
	list<edge>::iterator iter;	

	if(dis[end]>=99999999)return -1;	
	key=false;

	while(!pri_q.empty())
	{
		nd=pri_q.top();
		pri_q.pop();

		if(key&&nd.to==start)
		{
			kth--;
			if(kth==0)return nd.v;
		}
		key=true;

		for(iter=pri[nd.to].begin() ; iter!=pri[nd.to].end() ; iter++)
		{
			ndt.to=iter->to;
			ndt.v=nd.v+iter->v;
			pri_q.push(ndt);
		}
	}	
	
	return -1;
}
	

int main()
{
	init();

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

	return 0;
}