最短路
温馨提示：如果下文档中没有做特殊提示，默认所有下标从\(1\)开始，并且默认\(n,m\)同阶
因为在生活当中，路径的长度大多为正数，没有特殊说明，不考虑长度为负数的情况
\(s\)为起点，\(t\)为终点
\(dis[i]\)表示熊起点到编号为\(i\)的点的最短路径长度
\(inf\)表示一个极大值
前置知识：
- 链式前向星
这里不会过多介绍，如果不会可以参考一下理解
for(register int i=head[x];i;i=e[i].nxt){
//表示存在一条从x到e[i].to的边，边权为e[i].d
}
-
一些循环语句基础
-
一些\(stl\)(函数库知识)
引导：
在生活当中，我们经常面对了许多路径规划问题，通常会考虑下列几种因素：红绿灯多少，道路长短，车流量多少。一般都是应用程序在帮我们做出判断和选择，而我们减少了对这一类问题的思考。
考虑如下问题。
在一张\(n\)个点\(m\)条边有向/无向图中，求点\(a\)到点\(b\)之间的最短路径。
上面就是有关这一类问题的最简化形式，接下来考虑通过集中不同的视角解决这个问题。
算法一：暴力。
题目要我们找出最短路径，我们就把所有的路径找出来，然后判断哪一个是最短的即可，时间复杂度巨大，在生活当中有时会浪费掉大量的枚举时间，经常不值得使用。
算法二：\(floyd\)。
这是一个可以求出全源最短路径的算法（求出任意两点之间的最短路）算法
我们考虑每次枚举一个中转点，然后暴力判断所有经过中转点的转移状态
如果我们设\(f[i][j]\)表示从点到点的最短路径，我们就可以列出如下转移
\(f[i][j]=min(f[i][j],f[i][k]+f[k][j])\)
这个算法的正确性不言而喻，时间复杂度为\(\Theta(n^3)\)
实现的过程当中，要注意，先枚举\(k\)，再枚举\(i,j\)，这里提供了一份参考代码
fr(k,1,n) fr(i,1,n) fr(j,1,n) f[i][j]=min(f[i][j],f[i][k]+f[k][j])
算法三：\(spfa\)
这个算法再现在一般不常用，但是再某些特定的情况下依然可以用到
这类最短路不能处理出现出现负环的情况，接下来会讲述这种情况如何特判
我们首先找到起点，然后将其加入队列，进行如下操作
-
取出并弹出队首，我们设其为\(x\)
-
找出所有\(x\)可以到的边，如果最短路答案可以更新就更新，在靠右更新的条件下插入队列
-
如果当前队列为空，就结束，否则重复操作\(12\)
在上述流程当中，如果一个点进队了\(n\)次，说明原图存在负环
参考代码如下：
inline void spfa(){
fr(i,1,n) dis[i]=inf;
dis[s]=0;
queue<int> q;
q.push(s);vis[s]=1;
while(!q.empty()){
int y;
y=q.front();
q.pop();
vis[y]=0;
for(register int i=head[y];i;i=e[i].nxt){
int to;
to=e[i].to;
if(dis[to]<=dis[y]+e[i].d) continue;
dis[to]=dis[y]+e[i].d;
if(!vis[to]) vis[to]=1,q.push(to);
}
}
}
这个算法时间复杂度是\(\Theta(km)\)，其中\(k\)是每个点的进队次数，在随机数据下表现优异，一般可以当作一个常数，但是存在一些数据可以卡到最坏时间\(\Theta(nm)\)
算法四：\(dijskra\)(+堆优化)
这个算法在信息学竞赛中较为常用，时间复杂度较为稳定且实现效率高
我们考虑优化算法三
我们发现，有很多没有用的状态被我们加入了队列当中，所以我们考虑把队列替换成优先队列\((priority\_queue)\)，然后每个点最多只可能入队一次，这个证明留给读者自行思考
但是要注意，这个算法不能判断负环，所以如果题目当中没有保证不出现负环，那么要不就使用算法三，要不然就使用一些处理技巧把负环去掉，至于使用什么类型的处理技巧要根据不同的题目来实现
时间复杂度为\(\Theta(n\ log\ n)\)
例题：
小明是一位美食家，由于尝尽了各地的美食，导致他的体重飞速增长，从而使得走路会给他带来沮丧值
小明现在手上有一个地图，其中标记出来了\(n\)个城市，编号为\(1-n\)，并且有\(m\)条连接\(n\)个城市的路径，每条路径是一个单向路，表示为：存在一条从\(u_i\)到\(v_i\)长度为\(w_i\)个单位的路径
他一开始在起点\(s\)
因为他没有更多的交通共工具，所以他只能用腿走路，规定每秒可以走一个单位长度的路径
每停留一秒钟的时间，小明就会积攒一点的沮丧值
问小明到每个城市的最小沮丧值为多少
给定\(n,m,s\)和每一条路径
- \(input:\)
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
- \(output:\)
0 2 4 3
\(n,m \leq 10^5\)
解法：
不难在题目中抽离出来一个最短路模型，然后使用\(dijkstra\)算法即可通过此题
代码实现如下：
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
int x=0;
bool f=0;
char c=getchar();
while (!isdigit(c))
f|=(c=='-'),c=getchar();
while (isdigit(c))
x=(x<<3)+(x<<1)+(c^48),c=getchar();
return f?-x:x;
}
void write(int x) {
if(x<0) {
putchar('-');
x=-x;
}
if(x>9) write(x/10);
putchar(x%10+'0');
}
inline void writepl(int x){write(x);putchar(' ');}
inline void writeln(int x){write(x);putchar('\n');}
const int Maxn=1e6+10,inf=1e13;
int n,m;
int k;
struct node{
int nxt;
int to;
int d;
}e[Maxn];
struct ddd{
int dis;
int pos;
bool operator < (const ddd &x) const {
return dis>x.dis;
}
};
int head[Maxn];
int cnt;
priority_queue<ddd> q;
int Dis[Maxn];
bool vis[Maxn];
inline void add(int u,int v,int w){
cnt++;
e[cnt].nxt=head[u];
head[u]=cnt;
e[cnt].to=v;
e[cnt].d=w;
}
inline void Dij(){
for(register int i=1;i<=n;++i)
Dis[i]=inf;
Dis[k]=0;
ddd tmp;
tmp.dis=0;
tmp.pos=k;
q.push(tmp);
while(!q.empty())
{
ddd Tmp;
Tmp=q.top();
q.pop();
if(vis[Tmp.pos])
continue;
vis[Tmp.pos]=1;
for(register int i=head[Tmp.pos];i;i=e[i].nxt)
{
if(Dis[e[i].to]>Tmp.dis+e[i].d)
{
Dis[e[i].to]=Tmp.dis+e[i].d;
ddd TTmp;
TTmp.dis=Dis[e[i].to];
TTmp.pos=e[i].to;
q.push(TTmp);
}
}
}
}
signed main(){
//请输入小明拿到的地图的：点数，边数，起点，请保证，起点的标号小屋点数
cout<<"请输入小明拿到的地图的：点数，边数，起点"<<endl;
n=read();
m=read();
k=read();
//请分别m条边每一条边的具体情况：入点，出点，边权（长度）
cout<<"请分别m条边每一条边的具体情况（每一条边一行，一行三个数）：入点，出点，边权（长度）"<<endl;
for(register int i=1;i<=m;++i)
{
int x,y,z;
x=read();
y=read();
z=read();
add(x,y,z);
}
Dij();
//小明到达每一个城市分别的沮丧值
cout<<"小明到达每一个城市分别的沮丧值"<<endl;
for(register int i=1;i<=n;++i)
{
printf("小明到达编号为%lld的城市会有%lld的沮丧值\n",i,Dis[i]);
//write(Dis[i]);
//putchar(' ');
}
return 0;
}