迪杰斯特拉算法
dis[s]=0; //距离设置为0 ,起点的距离设置为0
q.push({0,s}); //入队列
while(q.size()) {
PII now=q.top(); //取优先队列队顶
q.pop();
int u=now.second;
vis[u]=1; //设置标记
for(int j=0; j<ve[u].size(); j++) {
int v=ve[u][j];
if(vis[v]==0) { //判断vis
if(dis[v]>dis[u]+mmap[u][v]) {
dis[v]=dis[u]+mmap[u][v];
q.push({dis[v],v});
}
}
}
}
维护多个值（点权/边权）
假设在最短路的条件下附加其他条件
过路费用最少（边权和最少）/ 召集人员最多 (点权和最多）
过路费用最少：
money[s]=0;//到达起点的边权为0
.......省略
if(dis[v]>dis[u]+mmap[u][v]) {
dis[v]=dis[u]+mmap[u][v];
money[v]=money[u]+value[u][v];//对过路费用维护
q.push({dis[v],v});
} else if(dis[v]==dis[u]+mmap[u][v]) {
if(money[v]>money[u]+value[u][v]) {
money[v]=money[u]+value[u][v];//最短路一样，取最少费用
}
}
召集人员最多：
people[s]=p[s]；// 到达起点能召集的总人数=起点的人数
.........省略
if(dis[v]>dis[u]+mmap[u][v]) {
dis[v]=dis[u]+mmap[u][v];
people[v]=people[u]+p[v];//people表示召集最多人数，p表示每个节点的权
q.push({dis[v],v});
} else if(dis[v]==dis[u]+mmap[u][v]) {
if(people[v]<people[u]+p[v]) {
people[v]=people[u]+p[v];
}
}
输出最短路径的条数
cnt[s]=1; //表示到达某个点的路径数
................省略 ，图不大的情况下，可以使用暴力的方法求最小的 dis[]
if(dis[v]>dis[u]+mmap[u][v]) {
cnt[v]=cnt[u]; // 修改最短路径个数
dis[v]=dis[u]+mmap[u][v];
people[v]=people[u]+p[v];
q.push({dis[v],v});
} else if(dis[v]==dis[u]+mmap[u][v]) {
cnt[v]+=cnt[u]; //累加最短路径个数
if(people[v]<people[u]+p[v]) {
people[v]=people[u]+p[v];
}
}
打印最短路径
将最短路径打印出来
需要利用记录 前置节点 和回溯的方法
把路径回溯出来
if(dis[v]>dis[u]+mmap[u][v]) {
pre[v]=u;//记录前置节点！
dis[v]=dis[u]+mmap[u][v];
people[v]=people[u]+p[v];
q.push({dis[v],v});
} else if(dis[v]==dis[u]+mmap[u][v]) {
if(people[v]<people[u]+p[v]) {
pre[v]=u; //记录前置节点
people[v]=people[u]+p[v];
}
}
打印：
void print(int k)
{
if(k==s) // s是起点，由题目条件给出
{
cout<<s;
return ;
}
print(pre[k]); //寻找这个节点的前置节点
cout<<" "<<k;
}
print(k); //k是 终点，由题目条件给出！
其他dp算法的打印操作
打印
|