1 #include <set>  2 #include <map>  3 #include <list>  4 #include <cmath>  5 #include <queue>  6 #include <stack>  7 #include <vector>  8 #include <bitset>  9 #include <string> 10 #include <cctype> 11 #include <cstdio> 12 #include <cstring> 13 #include <cstdlib> 14 #include <iostream> 15 #include <algorithm> 16 // #include <unordered_map> 17  18 using namespace std; 19  20 typedef long long ll; 21 typedef unsigned long long ull; 22 typedef pair<int, int> pii; 23 typedef pair<ull, ull> puu; 24  25 #define inf (0x3f3f3f3f) 26 #define lnf (0x3f3f3f3f3f3f3f3f) 27 #define eps (1e-9) 28 #define fi first 29 #define se second 30  31 bool sgn(double a, string select, double b) { 32     if(select == "==")return fabs(a - b) < eps; 33     if(select == "!=")return fabs(a - b) > eps; 34     if(select == "<")return a - b < -eps; 35     if(select == "<=")return a - b < eps; 36     if(select == ">")return a - b > eps; 37     if(select == ">=")return a - b > -eps; 38 } 39  40  41 //-------------------------- 42  43 const ll mod = 1000000007; 44 const int maxn = 100010; 45  46 //use to bfs 47 struct Node { 48     int v, c; 49     int kind; 50     Node(int _v = 0, int _c = 0, int _kind = 0) { 51         v = _v, c = _c, kind = _kind; 52     } 53     bool operator<(const Node &a)const { 54         return c > a.c; 55     } 56 }; 57  58 //first is ‘v‘ , second is ‘cost‘ 59 vector<pii> edge[maxn]; 60 bool vis[maxn][2]; 61 int dist[maxn][2]; 62 int sav[maxn][2]; 63  64 void addedge(int u, int v, int w) { 65     edge[u].push_back(make_pair(v, w)); 66 } 67  68  69  70 // id from 1 71 int  dijkstra_heap(int n, int start, int stop) { 72     memset(vis, 0, sizeof(vis)); 73     memset(sav, 0, sizeof(sav)); 74     for(int i = 1; i <= n; i++) dist[i][0] = dist[i][1] = inf; 75     priority_queue<Node> que; 76     while(!que.empty())que.pop(); 77     dist[start][0] = 0; 78     sav[start][0] = 1; 79     que.push(Node(start, 0, 0)); 80     Node tmp; 81     while(!que.empty()) { 82         tmp = que.top(); 83         que.pop(); 84         int u = tmp.v; 85         int kind = tmp.kind; 86         if(vis[u][kind])continue; 87         vis[u][kind] = true; 88         for(int i = 0; i < edge[u].size(); i++) { 89             int v = edge[u][i].fi; 90             int cost = edge[u][i].se; 91             if(dist[u][kind] + cost < dist[v][0]) { 92                 dist[v][1] = dist[v][0]; 93                 sav[v][1] = sav[v][0]; 94                 dist[v][0] = dist[u][kind] + cost; 95                 sav[v][0] = sav[u][kind]; 96                 que.push(Node(v, dist[v][0], 0)); 97                 que.push(Node(v, dist[v][1], 1)); 98             } else if(dist[u][kind] + cost == dist[v][0]) { 99                 sav[v][0] += sav[u][kind];100             } else if(dist[u][kind] + cost < dist[v][1]) {101                 dist[v][1] = dist[u][kind] + cost;102                 sav[v][1] = sav[u][kind];103                 que.push(Node(v, dist[v][1], 1));104             } else if(dist[u][kind] + cost == dist[v][1]) {105                 sav[v][1] += sav[u][kind];106             }107         }108     }109     if(dist[stop][0] + 1 == dist[stop][1])return sav[stop][0] + sav[stop][1];110     return sav[stop][0];111 }112 113 int s, t;114 int n, m;115 116 117 void solve() {118     int kase;119     scanf("%d", &kase);120     while(kase--) {121         for(int i = 1; i <= n; i++) {122             edge[i].clear();123         }124         scanf("%d%d", &n, &m);125         int u, v, w;126         for(int i = 0; i < m; i++) {127             scanf("%d%d%d", &u, &v, &w);128             addedge(u, v, w);129         }130         scanf("%d%d", &s, &t);131         int ans = dijkstra_heap(n, s, t);132         printf("%d\n", ans );133     }134 135 }136 137 int main() {138 139 #ifndef ONLINE_JUDGE140     freopen("1.in", "r", stdin);141     freopen("1.out", "w", stdout);142 #endif143     // iostream::sync_with_stdio(false);144     solve();145     return 0;146 }