PAT1003有个测试点过不去，谢谢
#include<stdio.h>PAT ACM 最短路径 c 测试
#include<limits.h>
#define maxsize 1000
int E[maxsize][maxsize];
int visited[maxsize];
int shortest[maxsize][2];
int maxteam[maxsize];
int team[maxsize];
int main()
{
int n,m,me,save,i,j,c1,c2,L,min,fmin;
scanf("%d %d %d %d",&n,&m,&me,&save);
for(i=0;i<n;i++)
scanf("%d",&team[i]);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
E[i][j]=INT_MAX;
for(i=0;i<m;i++)
{
scanf("%d %d %d",&c1,&c2,&L);
if(E[c1][c2]>L)
E[c1][c2]=L;
E[c2][c1]=E[c1][c2];
}
for(i=0;i<n;i++)
{
visited[i]=0;
maxteam[i]=0;
shortest[i][0]=INT_MAX;
shortest[i][1]=0;
}
visited[me]=1;
maxteam[me]=team[me];
shortest[me][0]=0;
shortest[me][1]=1;
i=me;
while(i!=save)
{
for(j=0;j<n;j++)
{
if(E[i][j]!=INT_MAX&&visited[j]==0)
{
if(shortest[i][0]+E[i][j]<shortest[j][0])
{
shortest[j][0]=shortest[i][0]+E[i][j];
shortest[j][1]=shortest[i][1];
maxteam[j]=maxteam[i]+team[j];
}
else
if(shortest[i][0]+E[i][j]==shortest[j][0])
{
shortest[j][1]++;
if(maxteam[i]+team[j]>maxteam[j])
maxteam[j]=maxteam[i]+team[j];
}
}
}
min=INT_MAX;
fmin=-1;
for(j=0;j<n;j++)
{
if(visited[j]==0&&shortest[j][0]<min)
{
min=shortest[j][0];
fmin=j;
}
}
if(fmin==-1)
break;
visited[fmin]=1;
i=fmin;
}
if(shortest[save][1]==0)
printf("1 %d\n",team[save]);
else
printf("%d %d\n",shortest[save][1],maxteam[save]);
return 0;
}
