考查點：Dijkstra算法

思路：直接用Dijkstra算法，但是·要增加num數組記錄每個點到起點的最短路徑數，判斷時候在相等時也要更新，同樣還要增加權值點的數組和最短路徑的總權值數組來更新最大權值，注意對起點各個參數的初始化。增加如下代碼即可：

if(vis[v]==false&&d[u]+G[u][v]<d[v]){                d[v]=d[u]+G[u][v];                ww[v]=ww[u]+w[v];                num[v]=num[u];            }else if(d[u]+G[u][v]==d[v]){                if(ww[u]+w[v]>ww[v])                    ww[v]=ww[u]+w[v];                num[v]+=num[u];            }存儲結構應用鄰接矩陣：
#define LOCAL#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <string>#include <vector>#include <map>#include <set>#include <queue>#include <stack>#define FOR(i, x, y) for(int i = x; i <= y; i++)#define rFOR(i, x, y) for(int i = x; i >= y; i--)#define MAXN 600#define oo 0x3f3f3f3fusing namespace std;int n,m;int num[MAXN];int G[MAXN][MAXN];int d[MAXN];int w[MAXN];int ww[MAXN];int vis[MAXN];void Dijkstra(int s){    fill(d,d+MAXN,oo);    d[s]=0;    ww[s]=w[s];    num[s]=1;    for(int i=0;i<n;i++){        int u=-1,MIN=oo;        for(int j=0;j<n;j++){            if(vis[j]==false&&d[j]<MIN){                u=j;MIN=d[j];            }        }        if(u==-1)return;        vis[u]=true;        for(int v=0;v<n;v++){            if(vis[v]==false&&d[u]+G[u][v]<d[v]){                d[v]=d[u]+G[u][v];                ww[v]=ww[u]+w[v];                num[v]=num[u];            }else if(d[u]+G[u][v]==d[v]){                if(ww[u]+w[v]>ww[v])                    ww[v]=ww[u]+w[v];                num[v]+=num[u];            }        }    }}int main(){    #ifdef LOCAL        freopen("data.in","r",stdin);        freopen("data.out","w",stdout);    #endif // LOCAL    int c1,c2;    scanf("%d%d%d%d",&n,&m,&c1,&c2);    fill(G[0],G[0]+MAXN*MAXN,oo);    FOR(i,0,n-1)    {        scanf("%d",&w[i]);    }    FOR(i,1,m)    {        int u,v,w;        scanf("%d%d%d",&u,&v,&w);        G[u][v]=w,G[v][u]=w;    }    Dijkstra(c1);    PRintf("%d %d",num[c2],ww[c2]);    return 0;}