Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- typedef long long LL;
- const int maxn = 100000 + 100;
- struct Node {
- int pos;
- LL dis;
- // 无参与有参构造函数
- Node() {}
- Node(int pos, LL dis) : pos(pos), dis(dis) {}
- };
- // 重载 Node 的小于运算符
- // 由于 priority_queue 默认为大顶堆,这里将 dis 的比较取反,可以得到关于 Node 的小顶堆
- bool operator<(const Node &a, const Node &b) {
- return a.dis > b.dis;
- }
- bool vis[maxn]; // 标记节点是否已确认最短路径,非常重要,没有这个判断可能 TLE
- LL dis[maxn]; // 记录最短距离
- vector<Node> G[maxn]; // 图的邻接表结构
- priority_queue<Node> que; // 用于快速得到距离最短的节点的优先队列
- void dij(int s) {
- // 将所有节点的距离初始化为“无穷大”
- // 该“无穷大”值可以与其它较小值相加且不发生溢出
- memset(dis, 0x3f, sizeof(dis));
- // 初始化起点距离为 0
- que.push(Node(s, 0));
- dis[s] = 0;
- while (!que.empty()) {
- // 从优先队列中取出距离最短的点
- Node tmp = que.top();
- que.pop();
- // 如果已取出过,直接 continue,不要再重复处理,不然会被极端数据卡 TLE
- if (vis[tmp.pos]) {
- continue;
- }
- vis[tmp.pos] = true;
- for (Node &node : G[tmp.pos]) {
- if (dis[node.pos] > tmp.dis + node.dis) {
- // 能通过 tmp.pos 走到 node.pos,且距离更短,就更新距离,且入堆
- dis[node.pos] = tmp.dis + node.dis;
- que.push(Node(node.pos, dis[node.pos]));
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement