HDU-3790-最短路径
题目要求先选最短的道路,如果没有最短路可选,即几条道路都相等,再考花费。用Dijkstra更快一些。在选出最短边的同时加上对应的花费就可以了。详细请看代码:#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define MAX 1002 #define inf 999999 int map[MAX][MAX],cost[MAX][MAX]; int n; void DJ(int st,int en)//Dijkstra 传入起点和终点 { int i,j,MIN,v; int flag[MAX],dis[MAX],value[MAX]; for(i=1;i<=n;i++) { dis[i]=map[st][i]; value[i]=cost[st][i];//与一般模板相似,多加一个花费而已 } memset(flag,0,sizeof(flag)); flag[st]=1; for(i=1;i<=n;i++) { MIN=inf; for(j=1;j<=n;j++) { if(!flag[j]&&MIN>dis[j]) { v=j; MIN=dis[j]; } } if(MIN==inf)break; flag[v]=1; for(j=1;j<=n;j++) { if(!flag[j]&&map[v][j]<inf) { if(dis[j]>dis[v]+map[v][j]) { dis[j]=dis[v]+map[v][j]; value[j]=value[v]+cost[v][j];//先选好边长,同时也把对应的花费加上 } else if(dis[j]==dis[v]+map[v][j])//如果路长相等,则优先花费小的 { if(value[j]>value[v]+cost[v][j]) value[j]=value[v]+cost[v][j]; } } } } cout<<dis[en]<<" "<<value[en]<<endl;//输出到终点的最短路和花费 } int main() { int i,j,m,a,b,d,p,st,en; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0&&m==0)break; //memset(map,inf,sizeof(map)); //memset(cost,inf,sizeof(cost)); for(i=1;i<=n;i++) for(j=1;j<=n;j++)//初始化为最大值,用for循环更快一些 { map[i][j]=inf; cost[i][j]=inf; } while(m--) { scanf("%d%d%d%d",&a,&b,&d,&p); if(d<map[a][b]||(d==map[a][b]&&p<cost[a][b])) { map[a][b]=map[b][a]=d; cost[a][b]=cost[b][a]=p;//开两个二维数组分别记录边长和花费 } } scanf("%d%d",&st,&en); DJ(st,en); } return 0; }
补充:软件开发 , C++ ,