首先题目链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805523835109376

算法没学好，这道题想了几天到处查，以下是一些很有用的资料。

参考https://www.bilibili.com/video/BV1JW411i731?p=81

和https://www.jianshu.com/p/23de23310376

看完了视频有点了解对比着人家的答案才一步一步写出自己的。里面注释比较多，主要是方便自己以后查看，另外没有是用结构体，而是使用一堆全局变量，看来还是学的不到家，不过好在可以使用。后面有空再改改。

#include<stdio.h>
#include<stdlib.h>

#define Inf INT_MAX
//#define Inf 2147483647  //PAT上传的时候要使用这条替换上面那条，因为它不识别 INT_MAX
#define MaxCity 500
 
int Graph[MaxCity][MaxCity]; //这个二维数组要初始化为Inf,因为两个城市之间没有路不就表示他们之间无限远嘛
int citys[MaxCity]; //citys[i]存放第i个城市救援队数目 
int path[MaxCity]; //path[i]存储第i个城市最短路径上的上一个城市的编号初始化为-1 
int dith[MaxCity]; //dith[i]存储第i个城市到出发点城市的最短距离，初始化为Inf 
int totalTeamNum[MaxCity]; //totalTeamNum[i]存储从起点到第i个城市所有路径上救援队总数目，初始化为0 
int totalPathNum[MaxCity]; //totalPathNum[i]存储从起点到第i个城市所有路径总数，初始化为0 
int collected[MaxCity]; //collected[i]==1表示第i个城市已经被收入最短路径的集合了，其初始化为0 

void Init()
{
    int i = 0;
    for(; i < MaxCity; i++)
    {
        path[i] = -1;
        dith[i] = Inf;
        collected[i] = 0;
        totalTeamNum[i] = 0;
        totalPathNum[i] = 0;
        int j = 0;
        for(; j < MaxCity; j++)
        {
            Graph[i][j] = Inf;
        }
    }
 } 

int SelectV(int cityNum)
{
    int r = -1;
    int min = Inf;
    int i = 0;
    for(; i < cityNum; i++)
    {
        if((collected[i] == 0) &&  (dith[i] < min))
        {
            min = dith[i];
            r = i;
        }
    }
    return r;
}

void Dijkstra(int s, int cityNum)
{
    int flag = 1; //标志位为1 表示要进行初始化 
    while(1)
    {
        int v = SelectV(cityNum); //该函数选择dith数组里面未访问的城市里面距离最小的一个 
        if(v == -1)
        {
            if(flag == 1)//初始化，也就是第一次输入的时候设定起始城市一些值
            {
                v = s;
                dith[v] = 0; //起始城市到自己的距离是0 
                totalPathNum[v] = 1; //起始时路径条数初始化为1 
                totalTeamNum[v] = citys[v]; //起始时队伍总数初始化为自己城市的队伍数量 
            }
            else 
            {
                break;
            }
        }
        collected[v] = 1;
        int i = 0;
        for(; i < cityNum; i++)//这个循环用来访问v的所有临近城市，因为v被设定为访问后会对于其相邻的城市的dith值产生影响
                              //所以重新访问和设置于其相邻且未被访问的城市的dith值 
        {
            if(Graph[v][i] < Inf)
            {
                if(collected[i] == 0)
                {
                    if(dith[v] + Graph[v][i] < dith[i])//更新与v临近的城市i的dith值 
                    {
                        dith[i] = dith[v] + Graph[v][i];
                        path[i] = v;   //更新城市i的上一个城市为v，这个path数组在我们这里可以去掉因为没用，我保留是因为看数据结构视频的时候人家有我就懒得换了，呵呵任性 
                        totalTeamNum[i] = totalTeamNum[v] + citys[i];
                        totalPathNum[i] =  totalPathNum[v];
                    }
                    else if(dith[v] + Graph[v][i] == dith[i]) //如果相等表示找到了另外一条最短路径 
                    {
                        if(totalTeamNum[i] < totalTeamNum[v] + citys[i])//注意城市i的队伍总数是沿着两条路径的最大值 
                            totalTeamNum[i] = totalTeamNum[v] + citys[i];
                        totalPathNum[i] +=  totalPathNum[v]; //更新最短路径条数，不是加+1而是合并两条路径的总条数 
                    }
                    
                }
            }
        }

        flag = 0;
        
    }
    
}



/*  样例输入 
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
*/
int main()
{
    Init();
    
    int cityNum = 0;
    int roadNum = 0;
    int myCity = 0;
    int targCity = 0;
    scanf("%d %d %d %d", &cityNum, &roadNum, &myCity, &targCity);
    
    int i = 0;
    for(; i < cityNum; i++)
    {
        scanf("%d", &citys[i]);
    }

    int j = 0; 
    for(; j < cityNum; j++)
    {
        int i = 0;
        for(; i < cityNum; i++)
        {
            Graph[j][i] = Inf;
        }
    }
    
    int city1 = 0;
    int city2 = 0;
    int length = 0;
    int k = 0;
    for(; k < roadNum; k++)
    {
        scanf("%d %d %d", &city1, &city2, &length);
        Graph[city1][city2] = Graph[city2][city1] = length;
    }
    
    //数据接收完毕，其中城市以及城市之间的路使用一个二维数组来表示。
    //Graph[i][j]里面存放的是城市i和j之间的道路长度 

    
    Dijkstra(myCity, cityNum);
    
    printf("%d %d", totalPathNum[targCity], totalTeamNum[targCity]);
    
    return 0;
}