03.

Dijkstra 算法的应用。核心是：边权和最小且点权和最大。

#include <iostream>
#include <algorithm>
#define Infinity 9999999

using namespace std;

//res[] stores weight of each vertix,that is,the number of rescue teams of each city
//pathnum[] stores the number of shortest paths from S to D
//resnum[] stores the biggest number of rescue teams we can call along the way from S to D
int edge[501][501],visit[501],res[501],dist[501],pathnum[501],resnum[501];
int N,M,S,D;

int main()
{
    fill(visit,visit+501,false);
    fill(dist,dist+501,Infinity);
    fill(res,res+501,0);
    fill(resnum,resnum+501,0);
    fill(pathnum,pathnum+501,0);
    fill(edge[0],edge[0]+501*501,Infinity);
    cin>>N>>M>>S>>D;
    for(int i=0;i<N;i++)
    {
        cin>>res[i];
    }
    for(int i=0;i<M;i++)
    {
        int c1,c2;
        cin>>c1>>c2;
        cin>>edge[c1][c2];
        edge[c2][c1]=edge[c1][c2];
    }
    
    dist[S]=0;
    pathnum[S]=1;
    resnum[S]=res[S];
    while(1)
    {
        int min=Infinity,u=-1;
        for(int i=0;i<N;i++)
        {
            if(visit[i]==false&&dist[i]<min)
            {
                min=dist[i];
                u=i;
            }
        }
        if(u==-1)break;
        visit[u]=true;
        for(int v=0;v<N;v++)
        {
            if(edge[u][v]<Infinity)
            {
                if(visit[v]==false&&dist[u]+edge[u][v]<dist[v])
                {
                    dist[v]=dist[u]+edge[u][v];
                    resnum[v]=resnum[u]+res[v];
                    pathnum[v]=pathnum[u];
                }
                else if(dist[u]+edge[u][v]==dist[v])
                {
                    if(resnum[u]+res[v]>resnum[v])
                        resnum[v]=resnum[u]+res[v];
                    pathnum[v]+=pathnum[u];
                }
            }
        }
    }
    
    cout<<pathnum[D]<<' '<<resnum[D];
}