Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
3.0 kB
2
Indexable
Never
#pragma GCC optimize ("O3")
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define pb push_back
#define rep(i,s, n) for(int i=s;i<n;++i)
#define repr(i,s, n) for(int i=n;i>=s;--i)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define sz(x) int(x.size())
#define bpc          __builtin_popcount
#define pii          pair<int, int>
#define pll          pair<ll, ll>
#define piii         pair<pii, int>
#define vpii         vector<pii>
#define vpll         vector<pll>
#define f first
#define s second
#define endl '\n'
#define each(x, a) for (auto& x : a)
#define mem(a, b) memset(a, b, sizeof(a))
#define sortall(x) sort(all(x))
#define szof(arr) sizeof(arr)/sizeof(arr[0])
#define rrep(i, n) repr(i, n-1)
#define trav(a, x) for (auto& a : x)
#define present(c, x) ((c).find(x) != (c).end())
#define cpresent(c, x) (find(all(c),x) != (c).end())
#define vpii         vector<pii>
#define vpll         vector<pll>
using namespace std;
using namespace __gnu_pbds;
using namespace __cxx11;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;

const int MOD = 1e9 + 7;
const int INF = INT_MAX;
const ll LL_INF = LLONG_MAX;
const ll sz = 2*10e5;

bool color[sz];
ll d[sz];
pll parent[sz];
bool w[sz];
vector<pair<ll,ll>> vc[sz];
int ways = 0;

void bfs(ll a,ll b){
    color[a] = 1;
    d[a] = 0;
    parent[a] = mp(-1,-1);
    queue<ll> q;
    q.push(a);
    while(!q.empty()){
        a = q.front();q.pop();
        color[a] = 1;
        if(a == b){
            return;
        }
        for(pll s : vc[a]){
            if(!color[s.f]){
                q.push(s.f);
                d[s.f] = d[a] + 1;
                parent[s.f] = mp(a,s.s);
            }
        }
    }
}

void dfs(ll b,ll a){
    w[parent[b].s] = 1;
    if(parent[b].f!=-1)
    dfs(parent[b].f,a);
}

void solve() {

    int n,m;
    cin>>n>>m;
    rep(i,0,m){
        ll a,b,c;
        cin>>a>>b>>c;
        vc[a].pb(mp(b,c));
        vc[b].pb(mp(a,c));
    }
    ll a,b;
    cin>>a>>b;
    if(a == b){
        cout<<0<<endl;return;
    }
    if(abs(a-b) == 1){
        cout<<1<<endl;return;
    }
    bfs(a,b);
    dfs(b,a);

    rep(i,0,sz){
        if(w[i])ways++;
    }
    cout<<ways<<endl;
    ways = 0;
    for (int i = 0; i <= n; ++i) {
        parent[i] = {0, 0};
        w[i] = false;
        color[i] = false;
        d[i] = 0;
        vc[i].clear();
    }

}


int main() {
    fio;
    int t=1;

    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
Leave a Comment