签到题……
题目传送门
SPFA算法
本人曾经写过一篇有关Bellman-ford的博，但就算是挂了优化的ford也只能过这道题的弱化版。
今天就先填个坑，先讲SPFA。
在这里我直接认为你们已经有一定图论基础，至少知道啥是松弛之类的……
什么？你不知道？请移步百度……
spfa算法的一般时间复杂度：\(O(KM)\)，M为边数，K为每个节点平均进队次数，经测试接近4，所以spfa一般情况下是很高效的。
spfa算法的最坏时间复杂度：\(O(NM)\)，spfa算法可以被恶意卡到与bellman-ford一样的效率。
spfa被认为在随机的稀疏图中表现出色。
SPFA伪代码：
queue<int>q;//这个队列可是spfa的重点所在！
int n,m,s;//n是点数，m是边数，s是源点
struct node{
int to,val;//用来邻接表存图的结构体，to是目标点，val是边权值
};
int dis[10001];//distance数组不用说
bool vis[10001];//vis数组的作用是标记是否在队列中
vector<node>gragh[10001];//邻接表存图
inline void spfa(){
for(int i=1;i<=n;i++){
if(i==s)continue;
dis[i]=0x3f3f3f3f;
}
//这个初始化，不用说。
int t;//t是当前到哪个点了
q.push(s);//q队列最开始push进s去
vis[s]=1;//给s点一个标记
while(!q.empty()){//spfa终止的标志是队列为空
t=q.front();q.pop();//我们取出队头的这个元素，赋给t
for(int i=0;i<gragh[t].size();i++){//遍历所有与t相连的点
if(dis[t]+gragh[t][i].val<dis[gragh[t][i].to]){//如果满足松弛条件
//注意这里，我们是满足松弛条件才进行松弛，而不是直接一个min解决，这是因为松弛后紧跟的是入队操作，也是spfa进行常数优化的重点
dis[gragh[t][i].to]=dis[t]+gragh[t][i].val;//松弛操作
if(!vis[gragh[t][i].to]){//判断，若被松弛的点没入队
q.push(gragh[t][i].to);//直接入队
vis[gragh[t][i].to]=1;//打上标记
}
}
}
vis[t]=0;//别忘了我们在开头把t点pop出来了，要把标记消掉。
}
}
本人的马蜂清奇，可能有人看不懂这个邻接表啥意思，实际很简单啊，我来贴一下输入代码就明白了
for(int i=1;i<=m;i++){
scanf("%d %d %d",&u,&v,&w);//依次输入入点，出点，边权值
gragh[u].push_back({v,w});//在入点那个vector里push一下destination和value。
}
我们来讲一下spfa是怎么对bellman-ford优化的：
首先，明确一点，一个点什么时候必须需要松弛操作？当且仅当与它相连的点发生了松弛时！
q队列中存放的时是进行了松弛后所影响到的有待松弛的点。
vis数组是给正在队列中的元素打标记的，防止元素重复进入队列。
这几句明白了，spfa基本就明白了。
spfa的基本思路：
- 初始化，将起点扔进队列，打上标记
把队头元素取出，并遍历与之相连的节点，如果能进行松弛则前往步骤3，不能跳过
对该节点进行松弛，如果该节点在队列中，跳过，不在队列中进行步骤4
将该节点扔进队列。
遍历结束后，消除原队头元素的标记（就是我们在步骤2中拿出来的那个），然后重复步骤2直到队列为空。
到这里，spfa就讲完了，蒟蒻自认为讲的很清楚……
dijkstra算法
原始算法
dijkstra算法是巧妙运用贪心求图上单源最短路径的算法，时间复杂度为\(O(n^2)\)
dijkstra只适用于边权为正的图，如果为负，则贪心性质遭到破坏。
伪代码：
int n,m,s;
bool vis[maxn];
int dis[amxn];
int now=s;
memset(dis,0x3f,sizeof(dis));
dis[sourse]=0;
struct node{
int to,val;
}
vector<node>gragh[maxn];
//算法主体开始
while(!vis[now]){
for(int i=0;i<gragh[now].size();i++){
dis[gragh[now][i].to]=min(dis[gragh[now][i].to],dis[now]+gragh[now][i].val);
}//对当前节点进行松弛操作
vis[now]=1;//给当前节点打标记
int minn=0x3f3f3f3f;
for(int i=1;i<=n;i++){//遍历所有点，在没有被打标记的点中找到dis最小的点，更新为now
if(vis[i]==0&&ans[i]<minn){
minn=ans[i];
now=i;
}
}
}
算法基本思路：
- 初始化，同其他算法基本一致
对当前点进行松弛，标记。
在没有被打标记的点中找到dis最小的点，更新当前点
重复2，直到所有点都被标记
思路大致就是这么个思路，但是，裸的dijkstra还是不行，我们为了追求更快的速度，看到了这里：
for(int i=1;i<=n;i++){//遍历所有点，在没有被打标记的点中找到dis最小的点，更新为now
if(vis[i]==0&&ans[i]<minn){
minn=ans[i];
now=i;
}
}
既然是动态维护序列最小值，我们想到了优先队列
堆优化
伪代码：
#define maxn 100001
#define maxm 200001
#define inf 0x3f3f3f3f
int n,m,s,u,v,w;
struct node{
int to,val;
};
bool vis[maxn];
vector<node>gragh[maxn];
int dis[maxn];
struct point{
int id,distance;
bool operator < (const point & a)const{//重载<，适用于结构体
return distance>a.distance;
}
};
priority_queue<point>q;
void dijkstra(){
for(int i=1;i<=n;i++){
if(i==s)continue;
dis[i]=inf;
}//初始化
q.push({s,0});//把起点扔进堆
while(!q.empty()){
point curr=q.top();q.pop();//取出队头
if(vis[curr.id])continue;//注意！这一句不能少，有可能堆中出现id相同但是distance不同的情况
vis[curr.id]=1;//vis数组在这里的意思是这个点进没进过堆。
for(int i=0;i<gragh[curr.id].size();i++){//遍历与之相连的所有点
if(dis[gragh[curr.id][i].to]>dis[curr.id]+gragh[curr.id][i].val){//若能松弛
dis[gragh[curr.id][i].to]=dis[curr.id]+gragh[curr.id][i].val;//松弛
q.push({gragh[curr.id][i].to,dis[gragh[curr.id][i].to]});//把被松弛的点扔进堆，格式{点的序号，当前distance}
}
}
}
}
这样优化，dijkstra就被优化到了这个复杂度：\(O(m log m)\)
对于大多数题这个复杂度稳过了。
