1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,l,r) for (int i=(l);i<=(r);++i)
#define REP(i,l,r) for (int i=(l);i<(r);++i)
#define RFOR(i,l,r) for (int i=(l);i>=(r);--i)
#define RREP(i,l,r) for (int i=(l);i>(r);--i)
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3fLL;
inline void readi(int &p){
p=0;int f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){p=(p<<1)+(p<<3)+c-'0';c=getchar();}
p=f*p;
}
inline void readl(ll &p){
p=0;int f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){p=(p<<1)+(p<<3)+c-'0';c=getchar();}
p=f*p;
}
struct node{
int Next,y,v;
}Pth[10005];
int head[1005],cnt;
inline void add(int x,int y,int v){
cnt++;
Pth[cnt].Next=head[x];
Pth[cnt].y=y;
Pth[cnt].v=v;
head[x]=cnt;
}
int n,m,s,f;
int d[1005][2],c[1005][2];
bool v[1005][2];
struct heap{
int v,x,ty;
bool operator < (const heap &b) const{
return v>b.v;
}
}S;
void dij(){
priority_queue <heap> q;
q.push({0,s,0});
while (!q.empty()){
heap t=q.top(); q.pop();
int x=t.x,ty=t.ty;
if (v[x][ty]) continue;
v[x][ty]=1;
for (int i=head[x];i;i=Pth[i].Next){
int y=Pth[i].y;
int z=t.v+Pth[i].v;
if (d[y][0]>z){
if (d[y][1]>d[y][0]){
d[y][1]=d[y][0];
c[y][1]=c[y][0];
q.push({d[y][1],y,1});
}
d[y][0]=z;
c[y][0]=c[x][ty];
q.push({d[y][0],y,0});
}else if (d[y][0]==z){
c[y][0]+=c[x][ty];
}else if (d[y][1]>z){
d[y][1]=z;
c[y][1]=c[x][ty];
q.push({d[y][1],y,1});
}else if (d[y][1]==z){
c[y][1]+=c[x][ty];
}
}
}
}
void solve(){
cnt=0; memset(head,0,sizeof head);
readi(n); readi(m);
FOR(i,1,m){
int x,y,c;
readi(x),readi(y),readi(c);
add(x,y,c);
}
readi(s),readi(f);
memset(d,0x3f,sizeof d);
memset(c,0,sizeof c);
memset(v,0,sizeof v);
d[s][0]=0,c[s][0]=1;
dij();
if (d[f][0]+1==d[f][1]) printf("%d\n",c[f][0]+c[f][1]);
else printf("%d\n",c[f][0]);
}
int main(){
int t; readi(t);
while (t--) solve();
return 0;
}
|
