洛谷 P1339 [USACO09OCT]热浪Heat Wave

头一次用dijkstra写题也是想试验一下,priority_queue的小根堆用的不熟。。让人不知所以。。。
应该有个这样的小窍门。pq的默认是搞大根堆的,直接想非常不好想,写排序规则的地方只写<号,然后写成“假设你就要把大数排在前面,即顺着pq排序规则走的规则,然后把符号一反即可”。 两种方法代码里都有: 注意!该题中的Dijkstra算法错误,请勿继续使用!错误问题在堆判断dis时不能做到实时动态更新,而将dis插入到堆排序的结构体中可以使得堆中重复插入点相同,路径值不同的结构体值,这样点同路径值小的可以传到堆顶,大的在到顶时被忽略。
没问题的版本参见:https://renjikai.com/luogu-p4779/

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
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int t, c, ts, te;
struct edge {
    int v, w;
    edge(int vv, int ww) { v = vv; w = ww; }
};
vector<edge> edges[2505];
int dis[2505];
bool inqueue[2505];
//bool visited[2505];
/*
struct cmp {
    bool operator () (int i1, int i2) {
        return dis[i1] > dis[i2];
    }
};
*/

void SPFA() {
    queue<int> q;
    dis[ts] = 0;
    inqueue[ts] = true;
    q.push(ts);
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        inqueue[node] = false;
        for (int i = 0; i < edges[node].size(); i++) {
            if (dis[edges[node][i].v] > dis[node] + edges[node][i].w) {
                dis[edges[node][i].v] = dis[node] + edges[node][i].w;
                if (!inqueue[edges[node][i].v])q.push(edges[node][i].v);
            }
        }
    }
}
/*
void dijkstra() {
    priority_queue<int,vector<int>,cmp> pq;
    dis[ts] = 0;
    pq.push(ts);
    while (!pq.empty()) {
        int node = pq.top();
        pq.pop();
        if (visited[node])continue;
        visited[node] = true;
        for (int i = 0; i < edges[node].size(); i++) {
            if (!visited[edges[node][i].v] && dis[edges[node][i].v] > dis[node] + edges[node][i].w) {
                //有可能存在一种情况:虽然没有轮到点i成为离已处理完毕的点集最近的点,但点i的距离值已经由其它处理中或处理完毕的点多次更新,所以松弛的第二个条件必须加入,这也是为什么cmp必须要用实时的数据
                dis[edges[node][i].v] = dis[node] + edges[node][i].w;
                pq.push(edges[node][i].v);
            }
        }
    }
}
*/

int main() {
    ios::sync_with_stdio(false);
    cin >> t >> c >> ts >> te;
    for (int i = 1; i <= c; i++) {
        int rs, re, ci;
        cin >> rs >> re >> ci;
        edges[rs].push_back(edge(re, ci));
        edges[re].push_back(edge(rs, ci));
    }
    memset(dis, 0x7f, sizeof(dis));
    SPFA();
    //dijkstra();
    cout << dis[te];
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注