hdu3750最短路径问题 很好的双限制最短路

最短路径问题Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3675    Accepted Submission(s): 1114


Problem DescriptionInputOutputSample InputSample Output

9 11

#include<stdio.h>#include<string.h>int n,m,min[1005],start,end,used[1005],cost[1005];struct haha{int value;int dis;}map[1005][1005];void init(){int i,j;for(i=1;i<=n;i++)for(j=1;j<=n;j++){if(i!=j){map[i][j].dis=999999999;map[i][j].value=999999999;}else{map[i][j].dis=0;map[i][j].value=0;}}}void find_ans(){int i,j,mm,pos,v=0;memset(used,0,sizeof(used));for(i=1;i<=n;i++){min[i]=map[start][i].dis;cost[i]=map[start][i].value;}min[start]=0;cost[start]=0;used[start]=1;for(i=2;i<=n;i++){mm=999999999;for(j=1;j<=n;j++){if(!used[j]&&mm>min[j]){mm=min[j];pos=j;}}if(mm==999999999) break;used[pos]=1;for(j=1;j<=n;j++){if(!used[j]&&min[pos]+map[pos][j].dis<min[j])//如果仅仅是大于说明没有多条路 只有一条唯一的最短路径{min[j]=min[pos]+map[pos][j].dis;cost[j]=cost[pos]+map[pos][j].value;}else  if(!used[j]&&min[pos]+map[pos][j].dis==min[j])//主要是这里 如果相等说明会有多条道路 能同时产生最短路 {if(cost[j]>cost[pos]+map[pos][j].value)//如果新路径需要的value比以前的更小 就更新 否则不更新cost[j]=cost[pos]+map[pos][j].value;}}}}int main(){int i,x,y,v,d;while(scanf("%d %d",&n,&m)!=EOF){if(n==0&&m==0) break;        init();for(i=1;i<=m;i++){scanf("%d %d %d %d",&x,&y,&d,&v);if(map[x][y].dis>d)//又要防止重边 好像所有的最短路都要考虑  变态{map[y][x].dis=map[x][y].dis=d;map[y][x].value=map[x][y].value=v;}}scanf("%d %d",&start,&end);find_ans();printf("%d %d\n",min[end],cost[end]);}return 0;}/*一开始木有思路  看了人家的解题报告才搞了出来 有点自卑了  阿弥陀佛*/