最短路
Dijkstra-朴素 O(n^2)
初始化距离数组, dist[1] = 0, dist[i] = inf;
for n次循环 每次循环确定一个min加入S集合中,n次之后就得出所有的最短距离
将不在S中dist_min的点->t
t->S加入最短路集合
用t更新到其他点的距离
Dijkstra-堆优化 O(mlogm)
利用邻接表,优先队列
在priorityqueue[HTMLREMOVED], greater[HTML_REMOVED] > heap;中将返回堆顶
利用堆顶来更新其他点,并加入堆中类似宽搜
Bellman_ford O(nm)
注意连锁想象需要备份, struct Edge{inta,b,c} Edge[M];
初始化dist, 松弛dist[x.b] = min(dist[x.b], backup[x.a]+x.w);
松弛k次,每次访问m条边
Spfa O(n)~O(nm)
利用队列优化仅加入修改过的地方
for k次
for 所有边利用宽搜模型去优化bellman_ford算法
更新队列中当前点的所有出边
Floyd O(n^3)
初始化d
k, i, j 去更新d
模板:
Dijkstra-朴素
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=150010;
int n,m;
int dist[N],e[N],ne[N],w[N],idx,h[N];
bool st[N];
#define PII pair<int,int>
void add(int a,int b,int c){
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int dj(){
memset(dist,0x3f3f3f3f,sizeof dist);
dist[1]=0;
priority_queue<PII,vector<PII>,greater<PII>> heap;
heap.push({0,1});
while(heap.size()){
auto t=heap.top();
heap.pop();
int ver=t.second,distance=t.first;
if(st[ver]){
continue;
}
st[ver]=true;
for(int i=h[ver];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j]>distance+w[i]){
dist[j]=distance+w[i];
heap.push({dist[j],j});
}
}
}
if(dist[n]==0x3f3f3f3f){
return -1;
}
return dist[n];
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof h);
while(m--){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
cout<<dj();
}
Dijkstra-堆优化
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=150010;
int n,m;
int dist[N],e[N],ne[N],w[N],idx,h[N];
bool st[N];
#define PII pair<int,int>
void add(int a,int b,int c){
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int dj(){
memset(dist,0x3f3f3f3f,sizeof dist);
dist[1]=0;
priority_queue<PII,vector<PII>,greater<PII>> heap;
heap.push({0,1});
while(heap.size()){
auto t=heap.top();
heap.pop();
int ver=t.second,distance=t.first;
if(st[ver]){
continue;
}
st[ver]=true;
for(int i=h[ver];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j]>distance+w[i]){
dist[j]=distance+w[i];
heap.push({dist[j],j});
}
}
}
if(dist[n]==0x3f3f3f3f){
return -1;
}
return dist[n];
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof h);
while(m--){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
cout<<dj();
}
Bellman_ford
#include<iostream>
#include<cstring>
using namespace std;
int n,m,k;
const int N=100010;
int dist[N],backup[N];
struct node{
int a,b,w;
}edge[N];
int b(){
memset(dist,0x3f3f3f3f,sizeof dist);
dist[1]=0;
for(int i=0;i<k;i++){
memcpy(backup,dist,sizeof backup);
for(int j=1;j<=m;j++){
int a=edge[j].a,b=edge[j].b,w=edge[j].w;
dist[b]=min(dist[b],backup[a]+w);
}
}
if(dist[n]>0x3f3f3f3f/2){
return 0x3f3f3f3f;
}
return dist[n];
}
int main(){
cin>>n>>m>>k;
for(int i=1;i<=m;i++){
int a,b,w;
cin>>a>>b>>w;
edge[i].a=a,edge[i].b=b,edge[i].w=w;
}
int t=b();
if(t==0x3f3f3f3f){
cout<<"impossible";
}else{
cout<<t;
}
}
Spfa
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int n,m;
const int N=100010;
int dist[N];
int idx,h[N],e[N],ne[N],w[N];
bool st[N];
void add(int a,int b,int c){
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int spfa(){
memset(dist,0x3f3f3f3f,sizeof dist);
dist[1]=0;
queue<int> q;
q.push(1);
st[1]=true;
while(q.size()){
int t=q.front();
q.pop();
st[t]=false;
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j]>dist[t]+w[i]){
dist[j]=dist[t]+w[i];
if(!st[j]){
q.push(j);
st[j]=true;
}
}
}
}
if(dist[n]==0x3f3f3f3f){
return -2;
}
return dist[n];
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof h);
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
int t=spfa();
if(t==-2){
cout<<"impossible";
}else{
cout<<dist[n];
}
}
Floyd
#include<iostream>
#include<cstring>
using namespace std;
const int N=210;
int f[N][N],n,m,k;
void floyd(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
}
}
}
int main(){
cin>>n>>m>>k;
for(int i=1;i<=200;i++){
for(int j=1;j<=200;j++){
if(i==j){
f[i][j]=0;
}else{
f[i][j]=0x3f3f3f3f;
}
}
}
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
f[a][b]=min(f[a][b],c);
}
floyd();
while(k--){
int a,b;
cin>>a>>b;
if(f[a][b]>0x3f3f3f3f/2){
puts("impossible");
}else{
cout<<f[a][b]<<endl;
}
}
}