Language: C++

#include <bits/stdc++.h>

using namespace std;
typedef long long nagai;

vector<vector<pair<int, nagai>>> g;

vector<nagai> d;
const nagai inf = 1e18;

struct cmp
{
	bool operator()(int a, int b)
	{
		if (d[a] != d[b])
			return d[a] < d[b];
		return a < b;
	}
};

vector<nagai> dij(int from)
{
	d.assign(g.size(), inf);
	d[from] = 0;
	set<int, cmp> st;
	st.insert(from);
	while (st.size())
	{
		int x = *st.begin();
		st.erase(st.begin());
		for (auto [b, c] : g[x])
		{
			if (c + d[x] < d[b])
			{
				st.erase(b);
				d[b] = c + d[x];
				st.insert(b);
			}
		}
	}
	return d;
}

nagai mod = 1e9 + 7;

vector<nagai> cntways(vector<nagai>& d, vector<vector<int>>& g, int from)
{
	vector<nagai> ans(d.size());
	ans[from] = 1;
	vector<int> ord(d.size());
	iota(ord.begin(), ord.end(), 0);
	sort(ord.begin(), ord.end(), [&](int a, int b)
			{
				return d[a] < d[b];
			});
	for (int x : ord)
	{
		for (int y : g[x])
		{
			ans[y] += ans[x];
			if (ans[y] >= mod)
				ans[y] -= mod;
		}
	}
	return ans;
}

bool intersects(int a, int b, int c, int d)
{
	a = max(a, c);
	b = min(b, d);
	return b > a;
}

int main()
{
	int n, m;
	ios::sync_with_stdio(false);
	cin >> n >> m;
	int s, t;
	cin >> s >> t;
	--s, --t;
	g.resize(n);
	for (int i = 0; i < m; ++i)
	{
		int a, b, c;
		cin >> a >> b >> c;
		--a, --b;
		g[a].emplace_back(b, c);
		g[b].emplace_back(a, c);
	}
	auto ds = dij(s), dt = dij(t);
	vector<vector<int>> gs(n), gt(n);
	for (int i = 0; i < n; ++i)
	{
		for (auto [x, y] : g[i])
		{
			if (ds[i] + y == ds[x])
				gs[i].push_back(x);
			if (dt[i] + y == dt[x])
				gt[i].push_back(x);
		}
	}
	auto cnts = cntways(ds, gs, s), cntt = cntways(dt, gt, t);
	nagai len = ds[t];
	nagai cntall = cnts[t] * cnts[t] % mod;
	for (int i = 0; i < n; ++i)
	{
		if (ds[i] + dt[i] != len)
			continue;
		if (ds[i] == dt[i])
		{
			cntall -= cnts[i] * cnts[i] % mod * cntt[i] % mod * cntt[i] % mod;
			if (cntall < 0)
				cntall += mod;
		}
		for (int j : gs[i])
		{
			if (ds[j] + dt[j] != len)
				continue;
			if (dt[j] + (ds[j] - ds[i]) != dt[i])
				continue;
			if (intersects(ds[i], ds[j], dt[j], dt[i]))
			{
				cntall -= cnts[i] * cnts[i] % mod * cntt[j] % mod * cntt[j] % mod;
				if (cntall < 0)
					cntall += mod;
			}
		}
	}
	cout << cntall << endl;
}


Compiler output:
In file included from /usr/include/c++/14/map:62,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:152,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_tree.h: In instantiation of 'static const _Key& std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_S_key(_Const_Link_type) [with _Key = int; _Val = int; _KeyOfValue = std::_Identity<int>; _Compare = cmp; _Alloc = std::allocator<int>; _Const_Link_type = const std::_Rb_tree_node<int>*]':
/usr/include/c++/14/bits/stl_tree.h:2116:47:   required from 'std::pair<std::_Rb_tree_node_base*, std::_Rb_tree_node_base*> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_get_insert_unique_pos(const key_type&) [with _Key = int; _Val = int; _KeyOfValue = std::_Identity<int>; _Compare = cmp; _Alloc = std::allocator<int>; key_type = int]'
 2116 |           __comp = _M_impl._M_key_compare(__k, _S_key(__x));
      |                                                ~~~~~~^~~~~
/usr/include/c++/14/bits/stl_tree.h:2169:4:   required from 'std::pair<std::_Rb_tree_iterator<_Val>, bool> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_unique(_Arg&&) [with _Arg = const int&; _Key = int; _Val = int; _KeyOfValue = std::_Identity<int>; _Compare = cmp; _Alloc = std::allocator<int>]'
 2169 |         = _M_get_insert_unique_pos(_KeyOfValue()(__v));
      |           ^~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_set.h:514:25:   required from 'std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(const value_type&) [with _Key = int; _Compare = cmp; _Alloc = std::allocator<int>; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree<int, int, std::_Identity<int>, cmp, std::allocator<int> >::const_iterator; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other = std::allocator<int>; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key> = __gnu_cxx::__alloc_traits<std::allocator<int>, int>::rebind<int>; typename _Alloc::value_type = int; value_type = int]'
  514 |           _M_t._M_insert_unique(__x);
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~
a.cc:26:11:   required from here
   26 |         st.insert(from);
      |         ~~~~~~~~~^~~~~~
/usr/include/c++/14/bits/stl_tree.h:768:15: error: static assertion failed: comparison object must be invocable as const
  768 |               is_invocable_v<const _Compare&, const _Key&, const _Key&>,
      |               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_tree.h:768:15: note: 'std::is_invocable_v<const cmp&, const int&, const int&>' evaluates to false