版本1

#include<bits/stdc++.h>
using namespace std;
const int maxn=505;
const int INF = 1e9+5;
int N,M,C1,C2,c1,c2,L;
int weights[maxn],w[maxn]; //点权值 和 每个顶点的最大点权 
int G[maxn][maxn];   //邻接矩阵图 
int d[maxn],num[maxn]; //d数组数最短路径 num数组是最短路径的数量 
bool vis[maxn]={false};
void Dijkstra(int s){
	fill(d,d+N,INF); //初始化最短距离为无穷
	d[s] = 0;  //起点的最短路径为0
	num[s]=1;
	w[s] = weights[s];
	for(int i=0;i<N;i++){
		int u = -1, Min=INF;
		for(int j=0;j<N;j++){
			if(vis[j]==false && d[j] < Min){ //没被访问过,且有最短路径,则挑选出来 
				Min = d[j];
				u = j;
			}
		}
		vis[u]=true;
		for(int v=0;v<N;v++){
			if(vis[v]==false && G[u][v]!=INF){
				if(d[u] + G[u][v] < d[v]){  //最短路径更新 
					d[v]=d[u] + G[u][v];    //路径最短 
					w[v]=w[u] + weights[v]; //点权最大 
					num[v] = num[u];  //路径数量没有增加,则顺延 
				}else if(d[u] + G[u][v] == d[v]){
					num[v] += num[u]; //路径数量增加
					if(w[u] + weights[v] > w[v]){
						w[v]=w[u] + weights[v];
					} 
				} 
			}
		} 
	}  
	
}
int main(){
	fill(G[0],G[0]+maxn*maxn,INF); //没有边的地方就为无穷大 
	scanf("%d%d%d%d",&N,&M,&C1,&C2);
	for(int i=0;i<N;i++){
	 	scanf("%d",&weights[i]); //保存点权 
	 }
	for(int i=0;i<M;i++){
		scanf("%d%d%d",&c1,&c2,&L);
		G[c1][c2]=L;  //路为无向图 
		G[c2][c1]=L;
	}
	Dijkstra(C1);
	printf("%d %d\n",num[C2],w[C2]);
	return 0;
}

版本2

Dijkstra + DFS

#include<bits/stdc++.h>
#include<vector>
using namespace std;
const int maxn=505;
const int INF = 1e9+5;
int N,M,C1,C2,c1,c2,L;
int weights[maxn]; //点权值 
int G[maxn][maxn];   //邻接矩阵图 
int d[maxn]; //d数组数最短路径 
bool vis[maxn]={false};
vector<int> pre[maxn];
void Dijkstra(int s){
	fill(d,d+N,INF); //初始化最短距离为无穷
	d[s] = 0;  //起点的最短路径为0
	for(int i=0;i<N;i++){
		int u = -1, Min=INF;
		for(int j=0;j<N;j++){
			if(vis[j]==false && d[j] < Min){ //没被访问过,且有最短路径,则挑选出来 
				Min = d[j];
				u = j;
			}
		}
		vis[u]=true;
		for(int v=0;v<N;v++){
			if(vis[v]==false && G[u][v]!=INF){
				if(d[u] + G[u][v] < d[v]){  //最短路径更新 
					d[v]=d[u] + G[u][v];    //路径最短 
					pre[v].clear();
					pre[v].push_back(u);  //有最优前驱,先清空 
				}else if(d[u] + G[u][v] == d[v]){
					pre[v].push_back(u);  //有重复最短路径,直接添加 
				} 
			}
		} 
	}  
	
}
int optvalue,total=0;
vector<int> path,tempPath;
void DFS(int v){ //递归式+边界
	if(v==C1){   //叶子节点 即起点 因为是倒着找回去的 最开始给的是终点 
		total++;
		tempPath.push_back(v);
		int dotvalue=0;  //点权
		for(int i=tempPath.size()-1;i >=0; i--){
			int id=tempPath[i];
			dotvalue += weights[id];  
		}
		if(dotvalue > optvalue) {
			optvalue = dotvalue;
			path.clear();
			for(int i=tempPath.size()-1;i >=0; i--){
				path.push_back(tempPath[i]);
			}
		}
		tempPath.pop_back();  
		return;   //终止条件 
	} 
	tempPath.push_back(v);
	for(int i=0;i<pre[v].size();i++){ //遍历pre[v]的所有结点并进行递归 
		DFS(pre[v][i]);
	} 
	tempPath.pop_back();
	
}
int main(){
	fill(G[0],G[0]+maxn*maxn,INF); //没有边的地方就为无穷大 
	scanf("%d%d%d%d",&N,&M,&C1,&C2);
	for(int i=0;i<N;i++){
	 	scanf("%d",&weights[i]); //保存点权 
	 }
	for(int i=0;i<M;i++){
		scanf("%d%d%d",&c1,&c2,&L);
		G[c1][c2]=L;  //路为无向图 
		G[c2][c1]=L;
	}
	Dijkstra(C1);
	DFS(C2);
	printf("%d %d\n",total,optvalue);
	return 0;
}