dijkstra算法
#include<iostream>
#include<algorithm> using namespace std; const int inf = 1000000000; int n; int road[502][502]; int cost[502]; bool mark[502]; int bypass[502],num[502]; int people[502]; int max1[502]; void dijksta(int s) { for(int i=0;i<n;i++) { cost[i]=inf; bypass[i]=inf; num[i]=0; mark[i]=false; } cost[s]=0; max1[s]=people[s]; num[s]=1; for(int j=0;j<n;j++) { int k=-1; for(int i=0;i<n;i++) { if((!mark[i])&&((k<0)||(cost[i]<cost[k]))) { k=i; //cout<<"k:"<<k<<endl; } } mark[k]=true; for(int i=0;i<n;i++) { if((!mark[i])&&(road[k][i]>0)) { int temp=cost[k]+road[k][i]; if(temp<cost[i]) { cost[i]=temp; num[i]=num[k]; max1[i]=max1[k]+people[i]; //cout<<people[i]<<endl; } else if(temp==cost[i]) { num[i]+=num[k]; int maymax=max1[k]+people[i]; if(maymax>max1[i]) { max1[i]=maymax; } } } } } } int main() { int m,start,end; cin>>n>>m>>start>>end; for(int i=0;i<n;i++) { cin>>people[i]; } for(int i=0;i<m;i++) { int a,b; cin>>a>>b; cin>>road[a][b]; road[b][a]=road[a][b]; } dijksta(start); //sort(cost,cost+n); //sort(num,num+n); cout<<num[end]<<" "<<max1[end]; return 0; }