记录编号	34000	评测结果	AAAAAAAAAA
题目名称	找最佳通路	最终得分	100
用户昵称	QhelDIV	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2011-11-24 21:51:29	内存使用	0.27 MiB

#include<fstream>
using namespace std;
ifstream fin("city.in");
ofstream fout("city.out");

int Map[51][51],D[51],n,MemberNum;
int From,To,NodePos[51];
bool flag[51];
class HEAP
{
public:
	int Data,Name;
	int Ls,Rs;
}heap[51];

void Swap(int *p,int *q)
{
	int tmp;
	tmp=*p;
	*p=*q;
	*q=tmp;
}

void Init()
{
int i;
int m;
	fin>>n>>m>>From>>To;
	int s,e;
	for(i=1;i<=m;i++)
	{
		fin>>s>>e;
		Map[s][e]=1;
	}
}
void Init_Single_Sourse()
{
	int i;
	for(i=1;i<=n;i++)
	{
		heap[i].Ls=i<<1;
		heap[i].Rs=heap[i].Ls+1;
	}
	heap[1].Name=From;
	NodePos[From]=1;
	MemberNum=1;
}

void Min_Heapify(int pos)
{
	int R,L,Minpos;
	R=heap[pos].Rs;
	L=heap[pos].Ls;
	Minpos=pos;
	
	if(L>=n && heap[Minpos].Data > heap[L].Data)
		Minpos=L;
	if(R>=n && heap[Minpos].Data > heap[R].Data)
		Minpos=R;
	if(Minpos!=pos)
	{
		Swap(&heap[Minpos].Data,&heap[pos].Data);
		Swap(&heap[Minpos].Name,&heap[pos].Name);
		Swap(&NodePos[heap[Minpos].Name],&NodePos[heap[pos].Name]);
		Min_Heapify(Minpos);
	}
}

void Dec(int pos)
{
int Next,i=pos;
	for(Next=i>>1; Next | 0; (i>>=1),(Next>>=1))
		if(heap[Next].Data > heap[i].Data)
		{
			Swap(&heap[i].Data,&heap[Next].Data);
			Swap(&heap[i].Name,&heap[Next].Name);
			Swap(&NodePos[heap[i].Name],&NodePos[heap[Next].Name]);
		}		
		else
			break;
}

void Extract_Min()
{
	NodePos[heap[MemberNum].Name]=1;
	
	Swap(&heap[1].Data,&heap[MemberNum].Data);
	Swap(&heap[1].Name,&heap[MemberNum].Name);
	
	NodePos[heap[MemberNum].Name]=0;
	
	MemberNum--;
	Min_Heapify(1);
}
void Dijkstra()
{
int Minpos,i;
	Init_Single_Sourse();
	for(;MemberNum | 0;)
	{
		Minpos=heap[1].Name;
		flag[Minpos]=true;
		NodePos[Minpos]=1;
		D[Minpos]=heap[1].Data;
		Extract_Min();
		for(i=1;i<=n;i++)
			if(Map[Minpos][i] && !flag[i])
			{
				if(NodePos[i]==0)
				{
					MemberNum++;
					heap[MemberNum].Data=D[Minpos]+Map[Minpos][i];
					heap[MemberNum].Name=i;
					NodePos[heap[MemberNum].Name]=MemberNum;
					Dec(MemberNum);
				}
				else
				{
					int U=Map[Minpos][i] + D[Minpos];
					if(U < heap[NodePos[i]].Data)
					{
						heap[NodePos[i]].Data=U;
						Dec(NodePos[i]);
					}
				}
			}
		
	}
}

int main()
{
	Init();
	
	Dijkstra();
	
	fout<<D[To]+1<<endl;
	
	fin.close();
	fout.close();
	return 0;
}
/*
		Swap(&,&);
		Swap(&,&);
		Swap(&,&);
*/