记录编号	546524	评测结果	AAAAAAAAAATT
题目名称	[POJ 3463] 观光	最终得分	83
用户昵称	瑆の時間~無盡輪迴·林蔭	是否通过	未通过
代码语言	C++	运行时间	2.540 s
提交时间	2019-11-10 00:31:58	内存使用	7.06 MiB

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
vector<pair<int,int> > b[1001],fb[1001];
int vis[1001],dis[1001];
int n,m,a1,a2,a3,S,F,ans,MX,T;
void DIJ()
{
	memset(dis,0x3f3f3f3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	priority_queue<pair<int,int> > q; 
	dis[F]=0;
	q.push(make_pair(0,F));
	while(q.size())
	{
		int u=q.top().second;
		q.pop();
		if(vis[u])
			continue;
		vis[u]=1;
		for(int i=0;i<fb[u].size();i++)
		{
			int to=fb[u][i].first;
			if(dis[to]>dis[u]+fb[u][i].second)
			{
				dis[to]=dis[u]+fb[u][i].second;
				q.push(make_pair(-dis[to],to));
			}
		}
	}
}
void ASTAR()
{
	priority_queue<pair<int,int> > q;
	q.push(make_pair(-dis[S],S));
	while(q.size())
	{
		int u=q.top().second;
		int v=q.top().first;
		q.pop();
		int dist=-v-dis[u];//实际上从起点到u的距离
		if(dist>MX)
			continue;
		if(u==F)
		{
			if(dist<=MX)
			{
				ans++;
			}
			else
				return;
		} 
		for(int i=0;i<b[u].size();i++)
		{
			int to=b[u][i].first;
			q.push(make_pair(-(dist+b[u][i].second+dis[to]),to));
		}
	}
}
int LINYIN()
{
	ans=0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		b[i].clear();
		fb[i].clear();
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&a1,&a2,&a3);
		fb[a2].push_back(make_pair(a1,a3));
		b[a1].push_back(make_pair(a2,a3));
	}
	scanf("%d%d",&S,&F);
	DIJ();
	MX=dis[S]+1;
	ASTAR();
	printf("%d\n",ans);
	return 0;
}
int LWH()
{
	freopen("sightseeing.in","r",stdin);
	freopen("sightseeing.out","w",stdout);
	scanf("%d",&T);
	while(T--)
	{
		LINYIN();
	}
	return 0;
}
int MYLOVE=LWH();
int main()
{
	;
}