[最短路SPFA]--启动！！！！！

基础模板

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define PII pair<int,int >
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 1e6+10;
int n,m,s;
//int cnt[N];
bool vis[N];
int dis[N];
vector<PII> v[N];
//bool suc = 0;
void spfa(int s)
{queue<int> q;for(int i=1;i<=n;i++){//v[i].clear();//1.测试多组数据，并且每组数据重新建边时加上dis[i] = 1e9;//vis[i] = 0;//cnt[i] = 0;//在1.的情况下，还要查询负环时加上}vis[s] = 1;dis[s] = 0;q.push(s);while(q.size()){int now = q.front();q.pop();vis[now] = 0;for(auto t:v[now]){int spot = t.fi,w = t.se;if(dis[spot]>dis[now]+w){//cnt[spot] = cnt[now]+1;//查询负环时加上//if(cnt[spot]>=n)//{//	suc= 1;// 	return;//}dis[spot] = dis[now]+w;if(vis[spot]==0){vis[spot]=1;q.push(spot);}} }}
}
int main()
{IOS;cin>>n>>m;while(m--){int a,b,w;cin>>a>>b>>w;v[a].pb({b,w});//v[b].pb({a,w});//双向边时候加上}cin>>s;//s为初始起点spfa(s);
}

P3371 【模板】单源最短路径（弱化版）

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define PII pair<int,int >
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 1e6+10;
int n,m,s;
vector< pair<int,int> > v[N];//v[s][i].fi是初始点s能走到的第i个的点，v[s][i].se初始点s能走到 
int dis[N];//是从初始点s到第i个点的最短路程 
bool vis[N];//标记该点是否被走过了 
void spfa()
{for(int i=1;i<=n;i++){dis[i] = 1e9;vis[i] = 0;	}queue<int> q;q.push(s);dis[s] = 0;vis[s] = 1;while(q.size()){int now = q.front();q.pop();vis[now] = 0;for(auto t:v[now]){int spot = t.fi,w =t.se;if(dis[spot]>dis[now]+w){dis[spot] = dis[now]+w; if(vis[spot]==0){vis[spot] = 1;q.push(spot);} }}}
}
int main()
{IOS;cin>>n>>m>>s;while(m--){int a,b,c;cin>>a>>b>>c;v[a].pb({b,c});//v[b].pb({a,c});加上为无向边，不加为单向边 }spfa();for(int i=1;i<=n;i++){if(dis[i]==1e9) cout<<(1ll<<31)-1<<' ';else cout<<dis[i]<<" ";}} 

P3385 【模板】负环

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define PII pair<int,int >
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 1e6+10;
int n,m;
bool vis[N];
int dis[N];
int cnt[N];//1.加个数组
vector<PII> v[N];
//2.cnt[i]表示走到第i个点时用了几条边,一般最大为n-1条,如果存在负环, 则会>=n  
bool spfa()//3.改为bool 
{queue<int> q;for(int i=1;i<=n;i++){dis[i] = 1e9;vis[i] = 0;cnt[i] = 0;//查负环时加上}//初始化vis[1] = 1;dis[1] = 0; q.push(1);while(q.size()){int now = q.front();q.pop();vis[now] = 0;for(auto t:v[now]){int spot = t.fi,w = t.se;if(dis[spot]>dis[now]+w){cnt[spot] = cnt[now]+1;//4.记录已用环数 if(cnt[spot]>=n) return true; //5.一定要返回,不然会一直重复去加负权 //如 5 -> 6边权为2, 6 -> 5边权为-3,便会一直+2-3下去，越加越爽，爽到负无穷  dis[spot] = dis[now]+w;if(vis[spot]==0){q.push(spot);vis[spot]=1;}}}}return false;//6.没有负环 
}
int main()
{IOS;int k;cin>>k;while(k--){cin>>n>>m;for(int i=1;i<=max(n,m);i++){v[i].clear();//多组数据时加上dis[i] = 1e9;vis[i] = 0;cnt[i] = 0;}while(m--){int a,b,c;cin>>a>>b>>c;if(c>=0) v[a].pb({b,c}),v[b].pb({a,c});else v[a].pb({b,c});}if(spfa()) cout<<"YES"<<"\n";else cout<<"NO"<<"\n";} }

那如果存在非连通的点呢？

	//从原点n+1开始搜bool spfa()//3.改为bool 
{queue<int> q;for(int i=1;i<=n;i++){dis[i] = 1e9;vis[i] = 0;cnt[i] = 0;//查负环时加上}//初始化vis[n+1] = 1;//从原点n+1开始搜，详情见7.--- dis[n+1] = 0; q.push(n+1);
} 
int main()
{for(int i=1;i<=n;i++)//7.注意!!如果各点可能不是全部连通，如果从1开始会搜不到另一部分的负权{                    //所以建立一个点把所有点连接起来，我们就设它为n+1v[n+1].pb({i,0});//从n+1开始到所有的点，边权为零不会影响结果 }
}

P3905 道路重建

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define PII pair<int,int >
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 1e6+10;
int n,m,d,A,B;
int dis[N];
bool vis[N];
vector<PII> v[N];
map<pair<int,int>,int> mp;
void spfa()
{for(int i=1;i<=n;i++){dis[i] = 1e9;vis[i] = 0;}//初始化queue<int> q;q.push(A);dis[A] = 0;vis[A] = 1;while(q.size()){int now = q.front();q.pop();vis[now] = 0;for(auto t:v[now]){int spot = t.fi,w = 0;  if(mp[{now,spot}]==1) w = t.se;//这条路如果被炸过了，那么就把他的长度算上，去修它 if(dis[spot]>dis[now]+w){dis[spot] = dis[now]+w; if(vis[spot]==0){vis[spot] = 1;q.push(spot);} }}}
}
int main()
{IOS;cin>>n>>m;while(m--){int a,b,c;cin>>a>>b>>c;v[a].pb({b,c});v[b].pb({a,c});}cin>>d;while(d--){int a,b;cin>>a>>b;mp[{a,b}] = 1;//标记a -> bb不能走 mp[{b,a}] = 1;//b -> a不能走 }cin>>A>>B;spfa();cout<<dis[B];
}

P1629 邮递员送信

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define PII pair<int,int >
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 1e6+10;
int n,m;
vector<PII> v1[N];
vector<PII> v2[N];
bool vis1[N];
int dis1[N];
bool vis2[N];
int dis2[N];
int sum=0;
void spfa1(int s)
{queue<int> q;vis1[s] = 1;for(int i=1;i<=n;i++){dis1[i] = 1e9;vis1[i] = 0;}//初始化dis1[s] = 0;q.push(s);while(q.size()){int now = q.front();q.pop();vis1[now] = 0;for(auto t:v1[now]){int spot = t.fi,w = t.se;if(dis1[spot]>dis1[now]+w){dis1[spot] = dis1[now]+w;if(vis1[spot]==0){vis1[spot] = 1;q.push(spot);}}}}
}
void spfa2(int s)
{queue<int> q;vis2[s] = 1;for(int i=1;i<=n;i++){dis2[i] = 1e9;vis2[i] = 0;}//初始化dis2[s] = 0;q.push(s);while(q.size()){int now = q.front();q.pop();vis2[now] = 0;for(auto t:v2[now]){int spot = t.fi,w = t.se;if(dis2[spot]>dis2[now]+w){dis2[spot] = dis2[now]+w;if(vis2[spot]==0){vis2[spot] = 1;q.push(spot);}}}}
}
int main()
{IOS;cin>>n>>m;while(m--){int a,b,l;cin>>a>>b>>l;v1[a].pb({b,l});v2[b].pb({a,l});//从所有的点走到1的路径，反向建边，让1替他们走一遍，避免了每个点都调用一次spfa导致超时} spfa1(1);spfa2(1);for(int i=1;i<=n;i++){sum+=dis1[i];sum+=dis2[i];}cout<<sum;
}

P2136 拉近距离

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define PII pair<int,int >
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 1e6+10;
int n,m,T;
int cnt[N];
bool vis[N];
int dis[N];
vector<PII> v[N];
bool suc = 0;
void spfa(int s)
{queue<int> q;for(int i=1;i<=n;i++){dis[i] = 1e9;vis[i] = 0;cnt[i] = 0;}vis[s] = 1;dis[s] = 0;q.push(s);while(q.size()){int now = q.front();q.pop();vis[now] = 0;for(auto t:v[now]){int spot = t.fi,w = t.se;if(dis[spot]>dis[now]-w){cnt[spot] = cnt[now]+1;if(cnt[spot]>=n){suc= 1;return;}dis[spot] = dis[now]-w;if(vis[spot]==0){vis[spot]=1;q.push(spot);}}}}
}
int main()
{IOS;cin>>n>>m;while(m--){int a,b,w;cin>>a>>b>>w;v[a].pb({b,w});}int minn=1e9;spfa(1);minn = min(minn,dis[n]);spfa(n);//小红也会干事情来拉近距离 ，靠!!!! minn = min(minn,dis[1]);if(suc) cout<<"Forever love";else cout<<minn;
}