bellman-ford：
因为最短路最多 \(n\) 点 \(n-1\) 边，则进行 \(n-1\) 轮操作，每轮枚举 \(m\) 边进行松弛即可。
时间复杂度 \(O(nm)\)。
spfa：
正确的称呼是队列优化的 bellman-ford。
我们知道，对于一个点，只有它被松弛了，它的邻接点才有可能被松弛。
于是我们用队列记录可能被松弛的点，每次只对这些点松弛即可。
同时我们用 vis 数组标记已进队的点，放置一个点进队多次。
T1
板子。
//bellman-ford
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5,M=5e5+5,MOD=1e5+3;
int n,m,s;
int dis[N];
bool vis[N];
struct edge{ int u,v,w; }e[M];
void bellman_ford(int s){
for(int i=1;i<=n;i++) dis[i]=2147483647;
dis[s]=0;
for(int i=1;i<n;i++)
for(int j=1;j<=m;j++)
if(dis[e[j].v]-e[j].w>dis[e[j].u])
dis[e[j].v]=dis[e[j].u]+e[j].w;
}
int main(){
cin>>n>>m>>s;
for(int i=1;i<=m;i++)
cin>>e[i].u>>e[i].v>>e[i].w;
bellman_ford(s);
for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
return 0;
}
//spfa
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5,M=5e5+5,MOD=1e5+3;
int n,m,s;
int dis[N];
bool vis[N];
struct edge{ int v,w; };
vector<edge> G[M];
void spfa(int s){
for(int i=1;i<=n;i++) dis[i]=2147483647;
dis[s]=0;
queue<int> q;
q.push(s),vis[s]=1;
while(!q.empty()){
int now=q.front(); q.pop();
vis[now]=0;
for(auto i:G[now]){
if(dis[i.v]>dis[now]+i.w){
dis[i.v]=dis[now]+i.w;
if(!vis[i.v]) vis[i.v]=1,q.push(i.v);
}
}
}
}
int main(){
cin>>n>>m>>s;
for(int i=1,u,v,w;i<=m;i++)
cin>>u>>v>>w,G[u].push_back({v,w});
spfa(s);
for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
return 0;
}
T2
加个等待过程即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,M=1e5+5;
int n,m;
int dis[N];
map<pair<int,int>,bool> o;
bool vis[N];
struct edge{ int v,w; };
vector<edge> G[M];
void spfa(){
memset(dis,0x3f,sizeof(dis));
queue<int> q;
q.push(1),vis[1]=1,dis[1]=0;
while(!q.empty()){
int now=q.front(); q.pop();
vis[now]=0;
int nd=dis[now];
while(o[{now,nd}]) nd++;
for(auto i:G[now]){
if(dis[i.v]>nd+i.w){
dis[i.v]=nd+i.w;
if(!vis[i.v]) vis[i.v]=1,q.push(i.v);
}
}
}
}
signed main(){
cin>>n>>m;
for(int i=1,u,v,w;i<=m;i++)
cin>>u>>v>>w,G[u].push_back({v,w}),G[v].push_back({u,w});
for(int i=1,k;i<=n;i++){
cin>>k;
for(int j=1,t;j<=k;j++) cin>>t,o[{i,t}]=1;
}
spfa();
cout<<(dis[n]==0x3f3f3f3f3f3f3f3f?-1:dis[n]);
return 0;
}
T3
dijkstra 记录路径并递归输出即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,M=1e5+5;
int n,m;
int dis[N],path[N];
bool vis[N];
struct edge{ int v,w; };
vector<edge> G[M];
struct node{
int u,w;
bool operator < (const node &b) const{
return w>b.w;
}
};
void dijkspfa(){
for(int i=1;i<=n;i++) dis[i]=1e18;
priority_queue<node> q;
q.push({1,0}),dis[1]=0;
while(!q.empty()){
node now=q.top(); q.pop();
if(vis[now.u]) continue; vis[now.u]=1;
for(auto i:G[now.u]){
if(dis[i.v]>dis[now.u]+i.w){
path[i.v]=now.u;
dis[i.v]=dis[now.u]+i.w;
q.push({i.v,dis[i.v]});
}
}
}
}
void print(int x){
if(x==1){ cout<<x<<' '; return; }
print(path[x]);
cout<<x<<' ';
}
signed main(){
cin>>n>>m;
for(int i=1,u,v,w;i<=m;i++)
cin>>u>>v>>w,G[u].push_back({v,w}),G[v].push_back({u,w});
dijkspfa();
if(dis[n]==1e18) cout<<-1;
else print(n);
return 0;
}
作业 T1
跑自己到自己的最长路即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5,M=5e5+5,MOD=1e5+3;
int n,m,t;
double dis[N];
bool vis[N];
map<string,int> id;
struct edge{ int v; double w; };
vector<edge> G[M];
void spfa(int s){
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++) dis[i]=-1e9;
dis[s]=1.0;
queue<int> q;
q.push(s),vis[s]=1;
while(!q.empty()){
int now=q.front(); q.pop();
vis[now]=0;
for(auto i:G[now]){
if(dis[i.v]<dis[now]*i.w){
dis[i.v]=dis[now]*i.w;
if(!vis[i.v]) vis[i.v]=1,q.push(i.v);
}
}
}
}
int main(){
while(cin>>n&&n){
for(int i=1;i<=n;i++) G[i].clear();
bool f=0;
++t;
for(int i=1;i<=n;i++){
string s; cin>>s,id[s]=i;
}
cin>>m;
for(int i=1;i<=m;i++){
string u,v; double w;
cin>>u>>w>>v,G[id[u]].push_back({id[v],w});
}
for(int i=1;i<=n;i++){
spfa(i);
if(dis[i]>1.0){
printf("Case %d: Yes\n",t),f=1;
break;
}
}
if(!f) printf("Case %d: No\n",t);
}
return 0;
}