0条评论
还没有人评论过~
#include "iostream" using namespace std; #define Max 500 #define Sky 99999 int Graph[Max][Max],Top,Start,End,Edge; int Dist[Max],Move[Max],Peo[Max],Sum[Max],Way[Max]; void Dis() { int i,j; for(i=0;i<Top;i++) { Dist[i]=Graph[Start][i]; Move[i]=false; if(i!=Start && Graph[Start][i]!=Sky) { Sum[i]=Peo[Start]+Peo[i]; Way[i]=1; } } Dist[Start]=0; Move[Start]=true; Sum[Start]=Peo[Start]; Way[Start]=1; for(i=1;i<=Top-2;i++) { int minw,maxp; minw=maxp=Sky; int k=Start; for(j=0;j<Top;j++) { if(!Move[j]) { if(minw>Dist[j]) { minw=Dist[j]; k=j; maxp=Sum[j]; } if(minw==Dist[j] && maxp<Sum[j]) { maxp=Sum[j]; k=j; } } } Move[k]=true; for(j=0;j<Top;j++) { if(!Move[j]) { if(Dist[j]==Dist[k]+Graph[k][j]) { Way[j]+=Way[k]; if(Sum[j]<Sum[k]+Peo[j]) { Sum[j]=Sum[k]+Peo[j]; } } if(Dist[j]>Dist[k]+Graph[k][j]) { Dist[j]=Dist[k]+Graph[k][j]; Sum[j]=Sum[k]+Peo[j]; Way[j]=Way[k]; } } } } } void Dfs(int end,int Sump) { if(end==Start) { return; } for(int j=0;j<Top;j++) { if(Sump-Peo[end]==Sum[j] && Dist[end]-Graph[end][j]==Dist[j]) { Dfs(j,Sum[j]); cout<<j<<" "; } } } int main( ) { //freopen("1.txt","r",stdin); cin>>Top>>Edge>>Start>>End; int i,j; for(i=0;i<Top;i++) for(j=0;j<Top;j++) Graph[i][j]=Sky; for(i=0;i<Top;i++) cin>>Peo[i]; for(i=0;i<Edge;i++) { int x,y,z; cin>>x>>y>>z; Graph[x][y]=Graph[y][x]=z; } Dis(); cout<<Way[End]<<" "<<Sum[End]<<endl; Dfs(End,Sum[End]); cout<<End<<endl; return 0; }