HDU 3790 最短路径问题

时间:2022-12-09 04:33:47

题目描述:求图上一个点到另一个点的最短距离 以及最小花费。

解题报告:这题用迪杰斯特拉算法是没有疑问,但是重点就是花费最小的问题,这个只要再开一个数组单独存放花费就可以了,其他的跟最短路径是一样的,但是这题我交了n次,就是 因为在输入的处理上,感觉这题也有点坑,题目上并没有说两个点之间可能有多条路径,但事实却是存在两个点之间有多条路径的可能,弄得我WA到死,后来看了别人的报告才发现,问题就出在我在取重复的路径的最小值的问题上,取最小值的时候千万不能简单的将路径跟花费分开求最小值,还要考虑到路径跟花费是有关系的,要更新必须经过特殊的处理,即先判断两点之间的长度是否大于后来输入的长度,如果是,则将这两点之间的长度和花费无条件更换,如果后来输入的长度跟原来的长度相等,那么在两条路径之间取花费较小的就可以了。代码附上:

HDU 3790 最短路径问题HDU 3790 最短路径问题
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 const int MAX = 1000+5,inf = 1061109568;
 5 int map[MAX][MAX][2],visit[MAX],T[MAX],cost[MAX],n,m;
 6 
 7 int main() {
 8     int a,b,d,p,s,e;
 9     while(scanf("%d%d",&n,&m),n+m) {
10         memset(map,0x3f,sizeof(map));
11         memset(cost,0x3f,sizeof(cost));
12         memset(T,0x3f,sizeof(T)); 
13         for(int i = 1;i<=m;++i) {
14             scanf("%d%d%d%d",&a,&b,&d,&p);
15             if(d<map[a][b][0]) {      //对于输入的处理很重要 
16                 map[a][b][0] = map[b][a][0] = d;
17                 map[a][b][1] = map[b][a][1] = p;
18             }
19             else if(d==map[a][b][0])
20             map[a][b][1] = map[b][a][1] = std::min(map[a][b][1],p);
21         }
22         scanf("%d%d",&s,&e);
23         T[s] = cost[s] = 0;   //将起点的花费和路径长度都赋0 
24         T[0] = inf-1;       //为便于更新s的值,将T[0]赋无穷大 
25         memset(visit,0,sizeof(visit));
26         while(1) {
27             for(int i = 1;i<=n;++i)
28             if(!visit[i]&&(T[s]+map[s][i][0])<=T[i]) {
29                 if(T[s]+map[s][i][0]<T[i]) { //这一步的处理很重要,要将等于和小于的情况分开处理 
30                     T[i] = T[s] + map[s][i][0];
31                     cost[i] = cost[s] + map[s][i][1];
32                 }
33                 else if(T[s]+map[s][i][0]==T[i])
34                 cost[i] = std::min(cost[i],cost[s] + map[s][i][1]);
35             }
36             visit[s] = 1;
37             s = 0; //将s做初始化处理 
38             bool flag = 1;

39             for(int i = 1;i<=n;++i)
40             if(!visit[i]&&T[i]<T[s]) {
41                 flag = 0;
42                 s = i;
43             }
44             if(flag) //设置退出条件 
45             break;
46         }
47         printf("%d %d\n",T[e],cost[e]);
48     }
49     return 0;
50 }
View Code