解析

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 1000;
const int INF = 0x3fffffff;
struct Node
{
	int v, w;
	Node(int _v, int _w) :v(_v), w(_w) { ; }
};
vector<vector<Node>> G;
int weight[1000]{ 0 };
vector<int> d, gather,num;
void dijksta(int s) {
	for (int i = 0; i < G.size(); i++) {
		d[i] = INF;
		gather[i] = 0;
		num[i] = 0;
	}
	d[s] = 0;
	gather[s] = weight[s];
	num[s] = 1;
	vector<bool> vis(G.size(), false);
	for (int i = 0; i < G.size(); i++) {
		int u = -1, min = INF;
		for (int j = 0; j < G.size(); j++) {   //找出最小
			if (vis[j] == false && d[j] < min) {
				u = j;
				min = d[j];
			}
		}
		vis[u] = true;
		for (auto x : G[u]) {   //对于连接顶点u的边
			if (vis[x.v] == false) {
				if (d[u] + x.w < d[x.v]) {
					d[x.v] = d[u] + x.w;
					gather[x.v] = gather[u] + weight[x.v];
					num[x.v] = num[u];
				}
				else if (d[u] + x.w == d[x.v]){
					if(gather[u]+weight[x.v] > gather[x.v])
						gather[x.v] = gather[u] + weight[x.v];
					num[x.v] += num[u];
				}
			}
		}
	}
}
int main()
{
	int N, M, city_in, city_save;
	scanf("%d %d %d %d", &N, &M, &city_in, &city_save);
	G.resize(N),d.resize(N),gather.resize(N),num.resize(N);
	for (int i = 0; i < N; i++)
		scanf("%d", &weight[i]);
	int city1, city2, len;
	for (int i = 0; i < M; i++) {
		scanf("%d %d %d", &city1, &city2, &len);
		G[city1].push_back(Node(city2, len));
		G[city2].push_back(Node(city1, len));
	}
	dijksta(city_in);
	printf("%d %d\n", num[city_save], gather[city_save]);
}

/*
5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1

*/