Dijkstra 算法小总结（未完）
前言：最短路问题在各种比赛中还是挺常见的，所以呢....还是很有必要好好弄懂的qwq
于是在洛谷上先看了模板题重新get了Dijkstra+堆优化的程序代码，然后做了几道最短路的题。现在做个小总结
PS：因为是刷题总结，所以就不像题解那样写得比较详细了。且因为是Dijkstra专题，所以以下所有最短路都是用Dijkstra+堆优化（或变式）来编
目录：
-
模板题
-
应用&变式题
模板题：
（两道模板题的唯一区别：数据范围不一样，弱化版的数据范围还要大一点？！）
如下给出标准版模板题的程序代码
#include <bits/stdc++.h>
using namespace std;
int n,m,s,tot;
int head[200001],dis[200001];
bool vis[200001];
struct edge{
int to,net,dis;
}e[200001];
struct node {
int dis,pos;
bool operator <( const node &x )const {
return x.dis<dis;
}
};
std::priority_queue<node> q;
inline void add_edge(int u,int v,int w) {
e[++tot].dis=w;
e[tot].to=v;
e[tot].net=head[u];
head[u]=tot;
}
inline void dijkstra() {
dis[s]=0;
q.push((node) {
0,s
});
while(!q.empty()) {
node tmp=q.top();
q.pop();
int x=tmp.pos,d=tmp.dis;
if(vis[x]) continue;
vis[x]=1;
for(register int i=head[x];i;i=e[i].net) {
int y=e[i].to;
if(dis[y]>dis[x]+e[i].dis) {
dis[y]=dis[x]+e[i].dis;
if(!vis[y]) {
q.push((node) {
dis[y],y
});
}
}
}
}
}
int main() {
scanf("%d%d%d",&n,&m,&s);
for(register int i=1;i<=n;i++) dis[i]=0x7fffffff;
for(register int i=1;i<=m;i++) {
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add_edge(u,v,w);
}
dijkstra();
for(register int i=1;i<=n;i++) printf("%d ",dis[i]);
return 0;
}
应用&变式：
这道题题目简明扼要，摆明了最短路嘛！只是需要注意是构建无向图，其他的直接套模板即可
再啰嗦一下构建无向图：就是重复两次调用add_edge（链式前向星建图），程序段如下：
inline void add_edge(int u,int v,int w) {
e[++tot].dis=w;
e[tot].to=v;
e[tot].net=head[u];
head[u]=tot;
}
for(register int i=1;i<=m;i++) {
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add_edge(u,v,w);
add_edge(v,u,w);
}
- 2、营救
联系一下生活实际，道路肯定是双向的嘛！所以是无向图
但是这道题还是有迷惑性的，一定要看完题，不能看到前面就直接认为是单纯的无向图最短路。题目的最后一句话：“一条从s至t的路线，使得经过道路的拥挤度最大值最小”，所以是求一定意义上的“最长路”！
所以我们只需要将板子里松弛操作，即只需要将原来的求和改成取max
Dijkstra（松弛操作）代码段如下：
inline void dijkstra() {
dis[s]=0;
q.push((node) {
0,s
});
while(!q.empty()) {
node tmp=q.top();
q.pop();
int x=tmp.pos,d=tmp.dis;
if(vis[x]) continue;
vis[x]=1;
for(register int i=head[x];i;i=e[i].net) {
int y=e[i].to;
if(dis[y]>max(dis[x],e[i].dis)) { //松弛操作
dis[y]=max(dis[x],e[i].dis);
if(!vis[y]) {
q.push((node) {
dis[y],y
});
}
}
}
}
}
- 3、最小花费
法（1）：题目中“A最少需要多少钱使得转账后B收到100元”提示我们这道题与模板题相对比，起点和终点相反。所以我们可以将A、B互换回来，再求最短路（最小花费）
法（2）：和上道题一样，也是修改松弛操作来实现这道题。因为题目给的转账方式是百分数，所以边权应该是相乘而不是相加！
注意一下法（2）中的一些小修改：
①优先队列中的重载小于号做了修改
②初始化的时候dis赋为0即可（负数应该也可），不要赋成正无限大
（亲试，如上两点不同时更改，样例都过不了QAQ，也有可能是我有些地方没注意，欢迎指出）
下面给出完成代码：
#include <bits/stdc++.h>
using namespace std;
int n,m,s,t;
int tot,head[1000001];
double dis[1000001];
bool vis[1000001];
struct edge {
int to,net;
double dis;
}e[1000001];
struct node {
double dis;
int pos;
bool operator < ( const node &x ) const {
return x.dis>dis;
}
};
std::priority_queue<node> q;
inline void add_edge(int u,int v,int w) {
e[++tot].dis=1.0-w/100.0;
e[tot].to=v;
e[tot].net=head[u];
head[u]=tot;
}
inline void dijkstra() {
dis[s]=1.0;
q.push((node) {
1.0,s
});
while(!q.empty()) {
node tmp=q.top();
q.pop();
int x=tmp.pos;
if(vis[x]) continue;
vis[x]=1;
for(register int i=head[x];i;i=e[i].net) {
int y=e[i].to;
if(dis[y]<dis[x]*e[i].dis) {
dis[y]=dis[x]*e[i].dis;
if(!vis[y]) {
q.push((node) {
dis[y],y
});
}
}
}
}
}
int main() {
scanf("%d%d",&n,&m);
for(register int i=1;i<=n;i++) dis[i]=0;
for(register int i=1;i<=m;i++) {
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add_edge(u,v,w);
add_edge(v,u,w);
}
scanf("%d%d",&s,&t);
dijkstra();
printf("%.8lf",100.0/dis[t]);
return 0;
}
感觉这题思路还是有点难度的（可能单纯因为我vegetable吧QAQ）
题目简述：
有n个点，m条路，对于每一条路给出两个端点（双向边哦）和这条路的花费、流量
要求求出1~n的道路的最大流量与最小花费的比×1e6（向下取整）
解题思路：
这题跟普通Dijkstra的区别就是有两个权值，所以我们先枚举1~1000（流量值最大1000）的流量值，然后每次都跑Dijkstra（起点始终是1，终点始终是n）
跑完一次我们就判断是否1~n连通，如果连通就比较答案的最大值
完整code：
#include <bits/stdc++.h>
using namespace std;
int n,m,a,b,c,f,tot,ans;
int dis[100010],vis[100010],head[100010];
priority_queue<pair<int,int> > shan;
struct node {
int to,net,liu,val;
} e[100010];
inline void add(int u,int v,int w,int l) {
e[++tot].to=v;
e[tot].net=head[u];
e[tot].liu=l;
e[tot].val=w;
head[u]=tot;
}
inline void dijkstra(int l) { //基本就是Dijkstra板子qvq
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[1]=0;
shan.push(make_pair(0,1)); //按照一维排序
while(!shan.empty()) {
int x=shan.top().second;
shan.pop();
if(vis[x]==1) continue;
vis[x]=1;
for(register int i=head[x];i;i=e[i].net) {
int v=e[i].to;
if(e[i].liu<l) continue; //如果流量值小于枚举值，不用执行了
if(dis[v]>dis[x]+e[i].val) {
dis[v]=dis[x]+e[i].val;
shan.push(make_pair(-dis[v],v));
}
}
}
}
int main() {
scanf("%d%d",&n,&m);
for(register int i=1;i<=m;i++) {
scanf("%d%d%d%d",&a,&b,&c,&f);
add(a,b,c,f); //双向边
add(b,a,c,f);
}
for(register int li=1;li<=1000;li++) { //枚举流量值
dijkstra(li);
if(dis[n]!=0x3f) ans=max(ans,int(double(li*1000000/dis[n]))); //如果连通就比较最大值
}
printf("%d",ans);
return 0;
}