记录编号	270119	评测结果	AAAAAAAAAA
题目名称	73.找最佳通路	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-06-14 14:28:17	内存使用	0.00 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=60,maxe=maxn*maxn;
template<typename T>//默认最小堆
struct Heap{
	static const int maxn=10010;
	T a[maxn];
	int len;
	Heap(){
		len=0;
	}
	void push(T sth){
		a[++len]=sth;
		for(int x=len;x^1;x>>=1){
			if(a[x]<a[x>>1]){
				T t=a[x];
				a[x]=a[x>>1];
				a[x>>1]=t;
			}
			else break;
		}
	}
	T& top(){
		return a[1];
	}
	T pop(){
		T res=a[1];
		a[1]=a[len--];
		for(int x=1,son;;x=son){
			if((x<<1)==len)son=x<<1;
			else if((x<<1)>len)break;
			else if(a[x<<1]<a[x<<1|1])son=x<<1;
			else son=x<<1|1;
			if(a[son]<a[x]){
				T t=a[x];
				a[x]=a[son];
				a[son]=t;
			}
			else break;
		}
		return res;
	}
	int size(){
		return len;
	}
	bool empty(){
		return !len;
	}
};
struct edge{
	int to,dis;
	edge* prev;
	edge():to(0),dis(0x7ffffff),prev(NULL){}
}ee[maxe];
struct node{
	int num,g,h;
	node(){}
	node(int num,int g,int h=0):num(num),g(g),h(h){}
	bool operator<(const node& x)const{
		return g+h<x.g+x.h;
	}
};
void insert(int,int,int);
void reinsert(int,int,int);
void dijkstra(int);
void Astar(int,int,int k);
int len=0;
edge* last[maxn]={NULL},*relast[maxn]={NULL};
bool vis[maxn];
int dis[maxn];
int n,m,s,t,x,y,z;
int MAIN(){
#define MINE
#ifdef MINE
	freopen("city.in","r",stdin);
	freopen("city.out","w",stdout);
#endif
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=0;i<m;i++){
		scanf("%d%d",&x,&y);
		insert(x,y,1);
	}
	dijkstra(s);
	printf("%d",dis[t]+1);
	return 0;
}
void insert(int x,int y,int z){
	ee[len].to=y;
	ee[len].dis=z;
	ee[len].prev=last[x];
	last[x]=&ee[len++];
}
void dijkstra(int x){
	int y;
	memset(vis,0,sizeof(vis));
	Heap<node>heap;
	heap.push(node(x,0));
	while(!heap.empty()){
		node b=heap.pop();
		x=b.num;
		vis[x]=true;
		dis[x]=b.g;
		if(x==t)return;
		for(edge* e=last[x];e;e=e->prev){
			y=e->to;
			if(vis[y])continue;
			heap.push(node(y,b.g+e->dis));
		}
	}
}
int haha=MAIN();
int main(){;}