记录编号	594347	评测结果	AAAAAAAAAAAA
题目名称	[POJ 3463] 观光	最终得分	100
用户昵称	袁书杰	是否通过	通过
代码语言	C++	运行时间	1.259 s
提交时间	2024-09-28 16:36:55	内存使用	4.19 MiB

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct edge{
	int u,v,w,nxt;
}e[2*10005];
int etot,head[10005],dis[10005],now,ans;
bool vis[10005],flag[10005];
void adde(int u,int v,int w){
	e[++etot]={u,v,w,head[u]};
	head[u]=etot;
}
struct node{
	int u,dis;
	bool operator<(const node&a)const{
		return a.dis<dis;
	}
};
priority_queue<node> q;
void dij(int s){
	for(int i=0; i<=10005; i++) {
		dis[i]=5e18;
	}
	q.push(node{s,0});
	dis[s]=0;
	while(!q.empty()){
		int u=q.top().u;
		q.pop();
		if(vis[u]){
			continue;
		}
		vis[u]=1;
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].v,w=e[i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push(node{v,dis[v]});
			}
		}
	}
}
int n,m,s,t;
void dfs(int u,int father,int len){
	if(u==t){
		if(len==now||len==now-1){
			ans++;
			return;
		}
	}
	if(len>now){
		return;
	}
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(!flag[v]){
			flag[u]=true;
			dfs(v,u,len+e[i].w);
			flag[u]=false;
		}
	}
}
signed main(){
	freopen("sightseeing.in","r",stdin);
	freopen("sightseeing.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		cin>>n>>m;
		memset(vis,0,sizeof(vis));
		memset(flag,0,sizeof(flag));
		memset(head,0,sizeof(head));
		etot=0;
		now=0;
		ans=0;
		memset(e,0,sizeof(e));
		for(int i=1;i<=m;i++){
			int u,v,w;
			cin>>u>>v>>w;
			adde(u,v,w);
		}
		cin>>s>>t;
		dij(s);
		now=dis[t]+1;
		dfs(s,0,0);
		cout<<ans<<'\n';
	}
	return 0;
}