最短路(floyd,dijkstra,spfa)

最短路

[floyd]
思考枚举k作为中转点来进行赋最小值，
原转移为a[k][i][j]=min(a[k][i][j],a[k-1][i][k-1],a[k-1][k-1][j]);
经空间压缩后为a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
注:为多远最短路 
核心代码:
void floyd(){
	for(int k=1;k<=n;k++){
	    for(int i=1;i<=n;i++){
	        for(int j=1;j<=n;j++){
	            a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
	        }
	    }
	} 
}
[dijkstra]
一种基于贪心的算法，每次弹出堆中的点，
对所有与其相连的点进行松弛操作，
然后将松弛成功且还未以其作为松弛起点的点加入堆，
准备下一次松弛。
(松弛，即查看以当前节点为中转点的最短路是否比目标节点的最短路小，小即更新)
注:无法处理负权 
核心代码:
typedef pair<int,int> P;
struct node{
	int to,len;
};
//dis为最短路径,mp为临接表,vis为标记数组
void dijkstra(int s){
	priority_queue<P,vector<P>,greater<P> >q;
	dis[s]=0;
	q.push(P{dis[s],s});
	while(!q.empty()){
		int l=q.top().second;
		q.pop();
		if(vis[l]){
			continue;
		}
		vis[l]=1;
		for(auto v:mp[l]) {
			if(dis[v.to]>dis[l]+v.len){
				dis[v.to]=dis[l]+v.len;
				q.push(P{dis[v.to],v.to});
			}
		}
	}
} 
[spfa]
每次弹出队列中的点对周围进行松弛操作，
将松弛成功的点加入队列（不论是否其已经为松弛起点过），
一直执行到没有点可以松弛。
所以spfa可以处理负权环，当一个点被松弛了n次及以上说明该处有负权环。
核心代码:
struct node{
	int to,len;
};
//数组意思同上 
void spfa(int s){
	queue<int>q;
	dis[s]=0;
	vis[s]=1;
	q.push(s);
	while(!q.empty()){
		int l=q.top();
		q.pop();
		vis[l]=0;
		for(auto v:mp[l]){
			if(dis[v.to]>dis[l]+v.len){
				dis[v.to]=dis[l]+v.len;
				if(!vis[l]){
					q.push(v.to);
					vis[l]=1;
				}
			}
		}
	}
}
1.
accoders【一本通图 最短路径算法】 信使 2004
思路:
打一个dijkstra的板子，注意是无向图。
code:
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
struct node{
	int to,len;
};
vector<node>mp[10010];
int dis[10010],vis[10010];
void dij(int s){
	priority_queue<P,vector<P>,greater<P> >q;
	dis[s]=0;
	q.push(P{dis[s],s});
	while(!q.empty()){
		int l=q.top().second;
		q.pop();
		if(vis[l]){
			continue;
		}
		vis[l]=1;
		for(auto v:mp[l]){
			if(dis[v.to]>dis[l]+v.len){
				dis[v.to]=dis[l]+v.len;
				q.push({dis[v.to],v.to});
			}
		}
	}
}
int main(){
	memset(dis,0x3f3f3f,sizeof dis);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int l,r,w;
		cin>>l>>r>>w;
		mp[l].push_back({r,w});
		mp[r].push_back({l,w});
	}
	dij(1);
	int ans=-1;
	for(int i=1;i<=n;i++){
		ans=max(ans,dis[i]);
	}
	if(ans>=0x3f3f00){
		cout<<-1;
	}else{
		cout<<ans;
	}
	int _=0;
	return (_^_^_);
}
2.
accoders 【一本通提高篇SPFA算法的优化】Wormholes 虫洞2117
思路:
用spfa判断负环。
code:
#include<bits/stdc++.h>
using namespace std;
const int N=1000010,inf=0x3f3f3f3f;
int T;
int n,m,k;
int num[N],dis[N],vis[N];
struct node{
	int to,len;
};
vector<node>e[N];
void init(){
	memset(dis,inf,sizeof dis);
	memset(num,0,sizeof num);
	memset(vis,0,sizeof vis);
	for(int i=1;i<=n;i++){
		e[i].clear();
	}
}
int spfa(int s){
	queue<int>q;
	dis[s]=0;
	q.push(s);
	vis[s]=1;
	num[s]=1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(auto v:e[u]){
			if(dis[v.to]>dis[u]+v.len){
				dis[v.to]=dis[u]+v.len;
				if(!vis[v.to]){
					num[v.to]++;
					if(num[v.to]>n-1){
						return 0;
					}
					q.push(v.to);
					vis[v.to]=1;
				}
			}
		}
	}
	return 1;
}
int main(){
	cin>>T;
	while(T--){
		cin>>n>>m>>k;
		init();
		for(int i=1;i<=m;i++){
			int u,v,w;
			cin>>u>>v>>w;
			e[u].push_back({v,w});
			e[v].push_back({u,w});
		}
		for(int i=1;i<=k;i++){
			int u,v,w;
			cin>>u>>v>>w;
			e[u].push_back({v,-w});
		}
		if(spfa(1)){
			cout<<"NO\n";
		}else{
			cout<<"YES\n";
		}
	}
	return 0;
}