hdu3790 最短路径

发表于 | 更新于 | 阅读次数：

HDU3790
简单的最短路径，Dijkstra做就行。有一点不同就是每条路径的属性除了距离，还有花费。解决方法是开一个花费数组cost，每添加一条路径后，记录一次花费。

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include<stdio.h>
using namespace std;

int ans;
struct CNode
{
    int k;  //有向边的终点
    int w; //权值
    int w0;
};

struct cmp
{
    bool operator () (CNode a, CNode b)
    {
        if(a.w==b.w)
            return a.w0>b.w0;
        return a.w > b.w;
    }
};

vector< vector<CNode> > S;    //整个图的邻接表

//小顶堆，用于保存未确定为最短路径的顶点
priority_queue<CNode, vector<CNode>, cmp> q;

int be,en;
int cost[1001];//花费
void dijkstra(int n)
{
    int d[1001]; //源点到i的距离
    memset(d, 0x3f, sizeof(d));
    CNode p;
    p.k = be;
    p.w = 0;
    //p.w0=0;
    q.push(p);
    d[be] = 0;
    cost[be]=0;
    while((!q.empty()))
    {
        p = q.top();    //取出最短的未确定顶点
        q.pop();
        if (d[p.k] < p.w)
            continue;
        for (int i = 0 ; i < S[p.k].size() ; i ++) // 以p.k为中间点，更新其他顶点的路径
        {
            //j为以p.k为起点的边的个数
            CNode t;
            t= S[p.k][i]; // 要更新路径长度的终点
            if (d[t.k] > d[p.k] + t.w) // 如果当前顶点可以以p.k为中间点更新路径
            {
                d[t.k] = d[p.k] + t.w;
                cost[t.k]= cost[p.k] +t.w0;
                t.w = d[t.k];
                q.push(t);

            }
            if(d[t.k] == d[p.k] + t.w)
            {
                cost[t.k]=min(cost[t.k],cost[p.k]+t.w0);
            }
        }
    }
    cout  << d[en] <<" ";
}

int main()
{
    //输入
    int n, m, a, b, c,d;
    while(scanf("%d%d",&n,&m),m||n)
    {
        ans=0;
        n++;
        S.clear();
        S.resize(n+1);
        CNode p1, p2;
        for (int i = 1 ; i <= m ; i ++)
        {
            scanf("%d%d%d%d",&a,&b,&c,&d);
            p1.k = b;
            p1.w = c;
            p1.w0= d;
            p2 = p1;
            p2.k = a;
            S[a].push_back(p1);
            S[b].push_back(p2);
        }
        scanf("%d%d",&be,&en);
        dijkstra(n);
        printf("%d\n",cost[en]);
    }
    return 0;
}

0%