Language: C++

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef pair<ll,int> pli;
typedef pair<int,int> ii;
typedef pair<int,ll> pil;
typedef vector<pil> vpil;
typedef pair<ii,ll> piil;
vector<vpil> graph;
vector<piil> edge;
int n,m;
int s,t;
vector<ll> ds,dt;
vector<ll> cnts,cntt;
const ll mod = 1e9 + 7;
void dijkstra(int start,vector<ll> &d,vector<ll> &cnt)
{
	cnt.assign(n+1,0ll);
	d.assign(n+1,-1);
	d[start] = 0ll;
	cnt[start] = 1ll;
	priority_queue<pli,vector<pil>,greater<pil> > pq;
	pq.push(pil(0ll,start));
	while(!pq.empty())
	{
		pli p = pq.top();pq.pop();
		ll x = p.first;
		int y = p.second;
		if(x==d[y])
		{
			for(int i=0;i<graph[y].size();++i)
			{
				pil q = graph[y][i];
				if(d[q.first]==-1)
				{
					cnt[q.first] = cnt[y];
					d[q.first] = d[y] + q.second;
					pq.push(pli(d[q.first],q.first));
				}
				else if(d[q.first]==d[y]+q.second)
				{
					cnt[q.first] = (cnt[q.first] + cnt[y])%mod;
				}
			}
		}
	}
} 
int main()
{
	int i,x,y;
	ll w;
	scanf("%d %d",&n,&m);
	scanf("%d %d",&s,&t);
	graph.assign(n+1,vpil());
	for(i=0;i<m;++i)
	{
		scanf("%d %d %lld",&x,&y,&w);
		graph[x].push_back(pil(y,w));
		graph[y].push_back(pil(x,w));
		edge.push_back(piil(ii(x,y),w));
	}
	dijkstra(s,ds,cnts);
	dijkstra(t,dt,cntt);
//	for(i=1;i<=n;++i)	printf("%lld ",ds[i]);	printf("\n");
//	for(i=1;i<=n;++i)	printf("%lld ",dt[i]);	printf("\n");
	ll dist = ds[t];
	for(i=1;i<=n;++i)
	{
		if(ds[i]+dt[i]!=dist)
		{
			cnts[i] = cntt[i] = 0ll;
		}
	}	
//	for(i=1;i<=n;++i)	printf("%lld ",cnts[i]);	printf("\n");
//	for(i=1;i<=n;++i)	printf("%lld ",cntt[i]);	printf("\n");
	ll ans = cntt[s] * cntt[s] % mod;
	for(i=0;i<m;++i)
	{
		piil k = edge[i];
		x = k.first.first;
		y = k.first.second;
		w = k.second;
		if(ds[x]+w+dt[y]==dist && abs(ds[x]-dt[y]) < w)
		{
	//		printf("%d %d\n",x,y);
			ans = (ans - cnts[x] * cntt[y] %mod+ mod) % mod;
		}
		if(dt[x]+w+ds[y]==dist && abs(dt[x]-ds[y]) < w)
		{
	//		printf("%d %d\n",x,y);
			ans = (ans - cntt[x] * cnts[y] %mod+ mod) % mod;
		}
	}
	for(i=1;i<=n;++i)
	{
		if(dt[i]+ds[i]==dist && dt[i]==ds[i])
		{
	//		printf("%d %d %d\n",i,cnts[i],cntt[i]);
			ans = (ans - cnts[i] * cntt[i] %mod+ mod) % mod;
		}
	}
	printf("%lld",ans);
}
/*
4 5
1 4
1 2 1
1 3 1
2 3 1
2 4 1
3 4 1
*/
/*
4 4
1 4
1 2 3
1 3 1
2 3 2
2 4 10
*/




Compiler output:
In file included from /usr/include/c++/14/queue:66,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:157,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_queue.h: In instantiation of 'class std::priority_queue<std::pair<long long int, int>, std::vector<std::pair<int, long long int> >, std::greater<std::pair<int, long long int> > >':
a.cc:23:48:   required from here
   23 |         priority_queue<pli,vector<pil>,greater<pil> > pq;
      |                                                       ^~
/usr/include/c++/14/bits/stl_queue.h:520:67: error: static assertion failed: value_type must be the same as the underlying container
  520 |       static_assert(is_same<_Tp, typename _Sequence::value_type>::value,
      |                                                                   ^~~~~
/usr/include/c++/14/bits/stl_queue.h:520:67: note: 'std::integral_constant<bool, false>::value' evaluates to false