hdu 3790 最短路径问题(最短路,Dijsktra)
Dijsktra基础题,只是多了一个花费,稍稍变动处理就好
#define _CRT_SECURE_NO_WARNINGS #include<string.h> #include<stdio.h> #include<math.h> #include<algorithm> using namespace std; const int MAXN=1010; #define typec int const typec INF=0x3f3f3f3f;//防止后面溢出,这个不能太大 bool vis[MAXN]; typec cost[MAXN][MAXN],huafei[MAXN][MAXN]; typec lowcost[MAXN],qihuafei[MAXN]; void Dijkstra(int n,int beg) { for(int i=1;i<=n;i++) { lowcost[i]=cost[beg][i];qihuafei[i]=huafei[beg][i];vis[i]=false; } for(int i=1;i<=n;i++) { typec temp=INF; int k=-1; for(int j=1;j<=n;j++) { if(!vis[j]&&lowcost[j]<temp) { temp=lowcost[j]; k=j; } } vis[k]=true; for(int l=1;l<=n;l++) { if(!vis[l]) { if(lowcost[l]>lowcost[k]+cost[k][l]) { lowcost[l]=lowcost[k]+cost[k][l]; qihuafei[l]=qihuafei[k]+huafei[k][l]; } if(lowcost[l]==lowcost[k]+cost[k][l]) { qihuafei[l]=min(qihuafei[l],qihuafei[k]+huafei[k][l]); } } } } } int main() { int n,m,i,j,s,t,a,b,c,d; 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++) huafei[i][j]=cost[i][j]=(i==j)? 0:INF; for(i=0;i<m;i++) { scanf("%d%d%d%d",&a,&b,&c,&d); if(cost[a][b]>c) { cost[a][b]=cost[b][a]=c; huafei[a][b]=huafei[b][a]=d; } } scanf("%d%d",&s,&t); Dijkstra(n,s); printf("%d %d\n",lowcost[t],qihuafei[t]); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。