单源最短路（自用）

基本思路

在简单图上求两点的最短距离，这里介绍dijstra算法。
按照bfs广度遍历的顺序向添加节点，再利用节点更新距离，被更新距离的节点要被添加进堆栈，然后继续更新距离，这样循环直至节点全部被更新。时间复杂度为O(n2)
有一种优化方法：用优先队列作为节点存储容器，按照权重从小到大排序，这样重复更新重复添加节点的次数会少一些。
实际上，该类问题属于模版题，要求记好模版及各变量的意义

流程

void dijstra(int l1,int r) {
memset(dist, 0x3f3f3f3f, sizeof(dist));
q.push({0,0});
dist[0] = 0;
while (!q.empty()) {
auto t = q.top();
q.pop();
int w = t.first;
int u = t.second;
for (auto t2 : g[u]) {
int v2 = t2.first;
int w2 = t2.second;
if (l1<=l[v2]&&l[v2]<=r&&dist[v2] > dist[u] + w2) {
dist[v2] = dist[u] + w2;
q.push({ dist[v2],v2 });
}
}
}
}

注意

首先明确建图方法；
有一种技巧：建立超级源点0。当所求问题在图上，但不易设置起点时（因为问题可以转化为起点到终点的最短路），可以人为设置起点0来指向目标终点，进而简化问题；
注意距离数组dist[]的初始化；