首页 > 代码库 > Hdu 3790 最短路径问题
Hdu 3790 最短路径问题
Problem地址：http://acm.hdu.edu.cn/showproblem.php?pid=3790
这道题的题目已经说明了这道题是求最短路径的问题。 |(*′口`)
这道题在算法并不算很难，只是在处理细节上需要注意。(?•??•?)??
如在输入时：1->2 距离是3 费用是2
2->1 距离是1 费用是5
要取距离1 费用5
1->2 距离是3 费用是2
2->1 距离是3 费用是5
要取距离3 费用2
这组数据来自这题的discuss，看了之后才明白我为什么WA了。o(╯□╰)o
同样对于时间的处理，不能分开处理：
假设运算中出现 s[t]=11,time[t]=5; //到目的地的时间为11，到目的地的时间为5
s[t]=10,time[t]=6;
此时错误的程序会取s[t]=10,time[t]=5。
所以按照题意应优先处理距离，如果运算中距离更新，则时间一定更新；
如果距离相同，则考虑时间是否需要更新。
我在这里采用了Dijstra算法，可能写的不算好，请见谅！
#include <iostream>#include <cstring>#include <cstdio>using namespace std;const int maxn = 1000+10;const int INF = 65524*64-1;int map[maxn][maxn];int price[maxn][maxn];int path[maxn];int cost[maxn];bool vis[maxn];int n,m,s,t;inline void input(){ int i,j; for(i=0;i<=n;i++) for(j=0;j<=n;j++) map[i][j]=price[i][j]=INF; int a,b,d,p; for( i=0;i<m;i++ ) { scanf("%d%d%d%d",&a,&b,&d,&p); //先比距离，再比时间 if( map[a][b]>d ) { map[a][b]=map[b][a]=d; price[a][b]=price[b][a]=p; } else if( map[a][b]==d ) { if(price[a][b]>p) price[a][b]=p; } } cin>>s>>t; return ;}inline void dijstra(){ int i; memset( vis,false,sizeof(vis) ); for( i=1;i<=n;i++ ) { path[i]=map[s][i]; cost[i]=price[s][i]; } vis[s]=true; path[s]=cost[s]=0; int count=0; int minC,k; while(count<n-1) { k=0; minC=INF; for( i=1;i<=n;i++ ) if( !vis[i] && minC>path[i] ) { minC=path[i]; k=i; } vis[k]=true; //先比距离，再比时间 for( i=1;i<=n;i++ ) if( !vis[i] && path[i] > path[k]+map[k][i] ) { path[i] = path[k]+map[k][i]; cost[i] = cost[k]+price[k][i]; } else if( !vis[i] && path[i] == path[k]+map[k][i] ) { if( cost[i] > cost[k]+price[k][i] ) cost[i] = cost[k]+price[k][i]; } count++; } return ;}int main(){ while(cin>>n>>m && (n||m)) { input(); dijstra(); cout<<path[t]<<" "<<cost[t]<<endl; } return 0;}
Hdu 3790 最短路径问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。