#include<iostream> #include<stdio.h> #include<stdlib.h> #include<math.h> #include<string.h> #include<algorithm> #include<map> #include<vector> #include<queue> using namespace std; //在dij基础上增加w[]和num[]数组 //w[u]表示从起点s到达顶点u可以得到的最大点权之和 //num[u]表示从起点s到达顶点u的最短路径条数 const int MAXV=510; //最大顶点数 const int INF=1000000000; //无穷大 //n为顶点数,m为边数,st和ed分别为起点和终点 //G为邻接矩阵,weight为点权 //d[]记录最短距离,w[]记录最大点权之和,num[]记录最短路径条数 int n,m,st,ed,G[MAXV][MAXV],weight[MAXV]; int d[MAXV],w[MAXV],num[MAXV]; bool vis[MAXV]={false};//vis[i]==true表示顶点i已访问,初值均为false void Dijkstra(int s){ //s为起点 fill(d,d+MAXV,INF); memset(num,0,sizeof(num)); memset(w,0,sizeof(w)); d[s]=0; w[s]=weight[s]; num[s]=1; for(int i=0;i<n;i++){ //循环n次 int u=-1,MIN=INF; //u使d[u]最小,MIN存放该最小的d[u] for(int j=0;j<n;j++){ //找到未访问的顶点中d[]中最小的 if(vis[j] == false && d[j] < MIN){ u=j; MIN=d[j]; } } //找不到小于INF的d[u]说明剩下的顶点和起点s不连通 if(u == -1) return ; vis[u]=true; //标记u为已访问 for(int v=0;v<n;v++){ //如果v未访问 && u能到达v && 以u为中介点可以使d[v]更优 if(vis[v]==false && G[u][v] != INF){ if(d[u]+G[u][v] < d[v]) { //以u为中介点时能令d[v]变小 d[v]=d[u]+G[u][v]; //覆盖d[v] w[v]=w[u]+weight[v]; //覆盖w[v] num[v]=num[u]; //覆盖num[v] }else if(d[u] + G[u][v] ==d[v]){ //找到一条相同长度的路径 if(w[u]+weight[v] > w[v]){ //以u为中介点时点权之和更大 w[v]=w[u]+weight[v]; //w[v]继承自w[u] } //最短路径条数与点权无关,必须写在外面 num[v] += num[u]; } } } } } int main(){ scanf("%d%d%d%d",&n,&m,&st,&ed); for(int i=0;i<n;i++){ scanf("%d",&weight[i]); //读入点权 } int u,v; fill(G[0],G[0]+MAXV*MAXV,INF); //初始化图G for(int i=0;i<m;i++){ scanf("%d%d",&u,&v); //边u--》v scanf("%d",&G[u][v]); //读入边权 G[v][u]=G[u][v]; //因为是无向图 } Dijkstra(st); //Dijkstra算法入口 printf("%d %d\n",num[ed],w[ed]); //最短距离条数,最短路径中的最大点权 system("pause"); return 0; }