zoj 2526 FatMouse and JavaBea...

zoj 2526 FatMouse and JavaBea...

#include<stdio.h>#include<string.h>#define inf 0x3fffffffint n,m,map[510][510],dp[510],mark[510],dis[510],w[510],pre[510],link[510];int st,ed;void dijkstra(){int i,j,k,min;memset(mark,0,sizeof(mark));memset(dp,0,sizeof(dp));memset(pre,-1,sizeof(pre));memset(link,0,sizeof(link));for(i=0;i<n;i++)dis[i]=inf;dis[st]=0;link[st]=1;dp[st]=w[st];for(i=0;i<n;i++){min=inf;k=-1;for(j=0;j<n;j++){if(!mark[j]&&min>dis[j]){min=dis[j];k=j;}}mark[k]=1;for(j=0;j<n;j++){if(mark[j]||dis[j]<dis[k]+map[k][j]||map[k][j]==inf)continue;if(dis[j]==dis[k]+map[k][j])link[j]+=link[k];else link[j]=link[k];if(dis[j]>dis[k]+map[k][j]||dp[j]<dp[k]+w[j]){dis[j]=dis[k]+map[k][j];pre[j]=k;dp[j]=dp[k]+w[j];}}}}void prit(int u){if(u==st){printf("%d",st);return;}prit(pre[u]);printf(" %d",u);}int main(){int i,j,x,y,p;while(scanf("%d%d%d%d",&n,&m,&st,&ed)!=-1){for(i=0;i<n;i++)for(j=0;j<n;j++)map[i][j]=inf;for(i=0;i<n;i++)scanf("%d",&w[i]);for(i=0;i<m;i++){scanf("%d%d%d",&x,&y,&p);if(map[x][y]>p)map[x][y]=map[y][x]=p;}dijkstra();printf("%d %dn",link[ed],dp[ed]);prit(ed);printf("n");}return 0;}