记录编号	594304	评测结果	AAAAAAAAAAAA
题目名称	[POJ 3463] 观光	最终得分	100
用户昵称	dream	是否通过	通过
代码语言	C++	运行时间	0.861 s
提交时间	2024-09-27 23:20:01	内存使用	5.49 MiB

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PI;
const int N=100005,M=200005;
int hd[N],to[M],nxt[M],val[M],dis[N],vis[N],tot;
int t,n,m,sdis,s,f,ans;
inline void read(int &x){
	char c;
	int sum=0,f=1;
	c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		sum=sum*10+c-'0'; 
		c=getchar();
	}
	x=sum*f;
}
void add(int x,int y,int v){
	tot++;
	to[tot]=y;
	val[tot]=v;
	nxt[tot]=hd[x];
	hd[x]=tot;
}
void dijkstra(){
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	priority_queue<PI,vector<PI>,greater<PI> > q;
	q.push({0,s});
	dis[s]=0;
	while(!q.empty()){
		PI t=q.top();
		q.pop();
		if(vis[t.second]){
			continue;
		} 
		vis[t.second]=1;
		for(int i=hd[t.second];i;i=nxt[i]){
			int y=to[i];
			if(dis[y]>dis[t.second]+val[i]){
				dis[y]=dis[t.second]+val[i];
				q.push({dis[y],y});
			}
		}
	}
	sdis=dis[f];
}
int mk[N];
void dfs(int u,int sum){
	if(sum>sdis+1){
		return;
	}
	if(u==f){
		if(sum==sdis+1||sum==sdis){
			ans++;
		}
		return;
	}
	int flag=0;
	for(int i=hd[u];i;i=nxt[i]){
		int y=to[i];
		if(mk[y]){
			continue;
		}
		mk[y]=1;
		dfs(y,sum+val[i]);
		mk[y]=0;
	}
}
int main(){
	freopen("sightseeing.in","r",stdin);
	freopen("sightseeing.out","w",stdout);
	read(t);
	while(t--){
		ans=0;
		read(n);
		read(m);
		memset(hd,0,sizeof(hd));
		memset(nxt,0,sizeof(nxt));
		tot=0;
		for(int i=1;i<=m;i++){
			int x,y,v;
			read(x);
			read(y);
			read(v);
			add(x,y,v);
		}
		read(s);
		read(f);
		dijkstra();
//		cout<<sdis<<"\n";
		dfs(s,0);
		printf("%d\n",ans);
	}
	return 0;
}