pyai's blog
0%

HDU-3790 最短路径问题

Posted on Edited on In Views:
  • 今天重新做了一下去年暑假被坑的题，当时真是年少无知，超时了以后就再也没尝试这道题，还是太菜了，不知道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;
}