0%

HDU-3790 最短路径问题

  • 今天重新做了一下去年暑假被坑的题,当时真是年少无知,超时了以后就再也没尝试这道题,还是太菜了,不知道cin和cout可以让我的程序超时,今天就把输入输出改了一下就过了,还是去年的代码,而且还是一个没优化的$O(N^2)$的$Dijkstra$算法。

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

题目内容如下:

​ 给你n个点,m条无向边,每条边都有长度d和花费p,给你起点s终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。

题解:

​ 首先还是$Dijkstra$就可以解决,因为还是求最短路径,只不过每个路径不再只是距离了,加了一个条件让求最短距离,并且最短距离多条时还要计算最少花费,也就是可以这样理解:在最短距离的松弛操作时,如果当前松弛结果比不松弛时小,那么此时不管松弛对花费造成什么影响都对花费进行松弛,因为首要目的时求最短距离,在保证最短距离时再求最少花费。如果松弛后没变,就理解为此时出现了多个最短距离,那么如果松弛操作可以使花费更少就进行松弛操作。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define MAX 1000010
#define LEN 1010
using namespace std;
int distD[LEN];
int distP[LEN];
int mapD[LEN][LEN];//路程
int mapP[LEN][LEN];//花费
bool visited[LEN];//标记某点是否被访问
//初始化
void init() {
int i,j;
for(i=0; i<LEN; i++) {
for(j=0; j<LEN; j++) {
mapD[i][j]=MAX;
mapP[i][j]=MAX;
}
}
}
//dijstra方法 n:多少个点 start:从某点开始
void dijstra(int n,int start) {
int i,j,min,k;
for(i=1; i<=n; i++) {
visited[i]=false;
distD[i]=mapD[start][i];
distP[i]=mapP[start][i];
}
visited[start]=true;
distD[start]=0;
for(i=1; i<=n; i++) {
min=MAX;
for(j=1; j<=n; j++) {
if(!visited[j] && distD[j]<min) {
min=distD[j];
k=j;
}
}
if(min==MAX) break;
visited[k]=true;
//只需要考虑距离就可以了
for(j=1; j<=n; j++) {
if(!visited[j]) {
if(distD[j]>distD[k]+mapD[k][j]) {
distD[j]=distD[k]+mapD[k][j];
distP[j]=distP[k]+mapP[k][j];
} else if(distD[j]==distD[k]+mapD[k][j]) { //如果路径相同
if(distP[j]>distP[k]+mapP[k][j]) {
distP[j]=distP[k]+mapP[k][j];
}
}
}
}
}
}
int main() {
int n,m;
while(scanf("%d%d",&n,&m)!=EOF) { //输入点和边
if(n==0&&m==0) break;
init();
int i,j,a,b,d,p,s,t;
for(i=0; i<m; i++) {
scanf("%d%d%d%d",&a,&b,&d,&p);
//cin>>a>>b>>d>>p;//输入各边的路径的花费
if(mapD[a][b]>d) {
mapD[a][b]=mapD[b][a]=d;
mapP[a][b]=mapP[b][a]=p;
}
}
scanf("%d%d",&s,&t);
//cin>>s>>t;//输入起始点和目标点
dijstra(n,s);
printf("%d %d\n",distD[t],distP[t]);
//cout<<distD[t]<<" "<<distP[t]<<endl;
}
return 0;
}
如果对您有帮助,请我喝杯奶茶?