头一次用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]; } |