1 #include<iostream>

 2 #include<cmath>

 3 #include<map>

 4 #include<cstring>

 5 #include<string>

 6 using namespace std;

 7 int n,m,start,ed;

 8 int p[550];//550是防止越界，也可以写510什么的，看个人习惯

 9 int g[550][550];

10 int cnt[550],sum[550];//cnt 是最短路径数 sum是救援队数量

11 bool st[550];//标志这个点是否抵达过

12 int f[550];//记录的是经过的点，这题可以理解成记录下标

13 int dist[550];

14 void print(int start,int ed)

15 {

16     if(ed==start)

17     {

18         cout<<start;

19         return;//起点就是终点

20     }

21     print(start,f[ed]);//递归不断回去,注意用DFS思想，从深向浅递归

22     cout<<" "<<ed;

23 }

24 void dj()

25 {

26     memset(dist,0x3f,sizeof dist);

27     dist[start]=0,cnt[start]=1,sum[start]=p[start];//初始化

28     for(int i=0;i<n;i++)

29     {

30         int t=-1;

31         for(int j=0;j<n;j++)

32         {

33             if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j;//取最短点

34         }

35         st[t]=true;

36         for(int j=0;j<n;j++)

37         {

38             if(dist[j]>dist[t]+g[t][j])//就是最短路变化

39             {

40                 f[j]=t;//记录路径,从t到j

41                 dist[j]=dist[t]+g[t][j];//变化最短路

42                 cnt[j]=cnt[t];//变化次数

43                 sum[j]=sum[t]+p[j];//最短路径变化后

44             }

45             else if(dist[j]==dist[t]+g[t][j])

46             {

47                 if(sum[j]<sum[t]+p[j])//救援队少的时候，变化路径

48                 {

49                     f[j]=t;

50                     sum[j]=sum[t]+p[j];

51                 }

52                 cnt[j]=cnt[j]+cnt[t];//两个最短路方式的相加

53             }

54         }

55     }

56 }

57 int main()

58 {

59     cin>>n>>m>>start>>ed;

60     for(int i=0;i<n;i++) cin>>p[i];

61     memset(g,0x3f,sizeof g);//设现在每一个城市间为正无穷的距离

62     for(int i=0;i<m;i++)

63     {

64         int a,b,c;

65         cin>>a>>b>>c;

66         g[a][b]=g[b][a]=min(g[a][b],c);//防止重边

67     }

68     dj();

69     cout<<cnt[ed]<<" "<<sum[ed]<<endl;

70     print(start,ed);

71     return 0;

72 }