1003 emergency (25 points), "DIJ deformation"

#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define dd double

#define PII pair<int,int>
#define int long long
using namespace std;
const dd eps = 1e-6;
const int mod = 1000003;
const int N = 1e3+10;
int n,m;
int c1,c2;
int cnt[N],sum[N];
int weight[N];
// cnt[j]  Deposit is j The number of shortest circuits to the starting point .
// sum[j]  Deposit is j The largest number of people on the shortest path to the starting point 
/*
n -  Number of cities 
m -  The number of roads 
c1 and c2  Cities that must be rescued 
*/
//#define int long long
const int INF = 0x3f3f3f3f3f3f3f3f;

int g[N][N], dist[N]; //  Dense graphs are stored in adjacency matrices 
bool st[N];

void dijkstra()
{
	//  The starting point is initialized to 0,  Other points are initialized to infinity (INF)
	memset(dist, 0x3f, sizeof dist);
	dist[c1] = 0;
	// The starting quantity is 1
	cnt[c1]=1;
	// Starting number is w1
	sum[c1]=weight[c1];
	for(int i = 1; i <= n; i++)
		{
			//  Find the point in which the shortest circuit is not currently determined   The shortest distance 
			int t = -1;
			for(int j = 0; j < n; j++)
				if(!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
			//  use t Update other points 
			for(int j = 0; j < n; j++)
			{
				if(dist[j]>dist[t]+g[t][j])
				{
					dist[j]=dist[t]+g[t][j];
					cnt[j]=cnt[t];
					sum[j]=sum[t]+weight[j];
				}
				else if(dist[j]==dist[t]+g[t][j])
				{
					cnt[j]+=cnt[t];
					sum[j]=max(sum[j],sum[t]+weight[j]);
				}
			}
			// t The shortest circuit has been determined 
			st[t] = true;
		}
	//  if INF It means there is no way 
}


signed main()
{
	// Input part 
	memset(g,0x3f,sizeof(g));
	cin>>n>>m>>c1>>c2;
	for(int i=0;i<n;i++)
	{
		cin>>weight[i];
	}
	for(int i=0;i<m;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		g[a][b]=g[b][a]=min(g[a][b],c);
	}
	dijkstra();
	cout<<cnt[c2]<<" "<<sum[c2]<<endl;
	return 0;
	//
}