杭电_3790_最短路径问题

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3790

这是上周四做的小训练的一个题目，最短路上稍微加了点，之前做的一个题目是直接求两点间最短路，现在不仅求出最短路，还有可能有多条最短路，现让你另外找出最短最便宜那条路。其实还是很简单。

作为一个最短路的练习吧。

代码：

#include<iostream>#include<cstring>#include<cstdio>#define inf 0xfffffffusing namespace std;#define size 1005int s[size][size];int c[size][size];bool visit[size];int dis[size];int cost[size];int n,m;void djk(int b,int e){ int i,j,tab,temp; memset(visit,0,sizeof(visit)); for(i=1;i<=n;i++) dis[i]=s[b][i],cost[i]=c[b][i]; dis[b]=0; cost[b]=0; visit[b]=1; for(i=1;i<n;i++) { temp=inf; for(j=1;j<=n;j++) { if(!visit[j]&&dis[j]<temp) temp=dis[j],tab=j; } visit[tab]=1; for(j=1;j<=n;j++) { if(!visit[j]&&dis[j]>dis[tab]+s[tab][j]) dis[j]=dis[tab]+s[tab][j],cost[j]=cost[tab]+c[tab][j]; else if(!visit[j]&&dis[j]==dis[tab]+s[tab][j]&&cost[j]>cost[tab]+c[tab][j]) cost[j]=cost[tab]+c[tab][j]; } }// cout<<dis[e]<<" "<<cost[e]<<endl; printf("%d %d\n",dis[e],cost[e]);}int main(){ int a,b,d,p,i,j,Start,End; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0&&m==0) break; for(i=1;i<=n;i++) for(j=1;j<=n;j++) s[i][j]=inf,c[i][j]=inf; for(i=0;i<m;i++) { //cin>>a>>b>>d>>p; scanf("%d%d%d%d",&a,&b,&d,&p); if(d<s[a][b]) { s[a][b]=s[b][a]=d; c[a][b]=c[b][a]=p; } } cin>>Start>>End; djk(Start,End); } return 0;}