记录编号	557969	评测结果	AAAAAAAAAAAA
题目名称	[POJ 3463] 观光	最终得分	100
用户昵称	数声风笛ovo	是否通过	通过
代码语言	C++	运行时间	1.528 s
提交时间	2020-12-02 23:04:26	内存使用	1.29 MiB

#include<bits/stdc++.h>
#define ll long long
#define pp cout<<"test\n"
using namespace std;
const int maxn=1e3+7,maxm=1e4+9;
bool vis[maxn];
int m,dis[maxn],n,s,f,ans,cnt,fcnt,head[maxn],fhead[maxn],maxx;
struct node{
	int from,to,next,dis;
}edge[maxm],fedge[maxm];
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
void build(int from,int to,int dis){
	edge[++cnt].from=from;
	edge[cnt].to=to;
	edge[cnt].dis=dis;
	edge[cnt].next=head[from];
	head[from]=cnt;
	return ;
}
void fbuild(int from,int to,int dis){
	fedge[++fcnt].from=from;
	fedge[fcnt].to=to;
	fedge[fcnt].dis=dis;
	fedge[fcnt].next=fhead[from];
	fhead[from]=fcnt;
	return ;
}
void dij(){
	priority_queue < pair<int,int> > q;
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	dis[f]=0;
	q.push(make_pair(0,f));
	while(!q.empty()){
		int u=q.top().second; q.pop();
		if(vis[u]) continue;
		vis[u]=true;
		for(int i=fhead[u];i;i=fedge[i].next){
			int v=fedge[i].to,d=fedge[i].dis;
			if(dis[v]>dis[u]+d){
				dis[v]=dis[u]+d;
				q.push(make_pair(-dis[v],v));
			}
		} 
	}
	return ; 
}
void Astar(){
	priority_queue < pair<int,int> > q;
	q.push(make_pair(-dis[s],s));
	while(!q.empty()){
		int d=q.top().first,u=q.top().second; q.pop();
		int dd=-d-dis[u];
		if(dd>maxx) continue;
		if(u==f){
			if(dd<=maxx) ans++;
			else return ;
		}
		for(int i=head[u];i;i=edge[i].next){
			int v=edge[i].to,ddd=d=edge[i].dis;
			q.push(make_pair(-(dd+ddd+dis[v]),v));
		}
	}
	return ;
}
int main(){
	freopen("sightseeing.in","r",stdin);
	freopen("sightseeing.out","w",stdout);
	int T;
	T=read();
	while(T--){
		ans=0; cnt=0; fcnt=0;
		memset(head,0,sizeof(head));
		memset(fhead,0,sizeof(fhead));
		n=read();m=read();
		for(int i=1;i<=m;i++){
			int x,y,z;
			x=read();y=read();z=read();
			build(x,y,z);
			fbuild(y,x,z);
		}
		s=read();f=read();
		dij();
		maxx=dis[s]+1;
		Astar();
		printf("%d\n",ans);
	}
	return 0;
}