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;
}