卡码网94： bellman_ford算法

算法思想
1.从边入手，对路径进行松弛操作
2.每次更新最短路径（松弛n-1）次

特：可有负权边，但是不能包含负权回路（可以判是否存在负权回路）

https://kamacoder.com/problempage.php?pid=1152
代码
朴素（不可判断负权回路）

include<bits/stdc++.h>

using namespace std;
int n,m;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
vector<vector>bian;
for(int i=0;i<m;i++)
{
int a,b,c;
cin>>a>>b>>c;
bian.push_back({a,b,c});
}
vectormisdis(n+1,INT_MAX);
misdis[1]=0;
for(int i=1;i<n;i++)
{
for(int j=0;j<m;j++)
{
int a=bian[j][0],b=bian[j][1],c=bian[j][2];
if(misdis[a]!=INT_MAX&&misdis[b]>c+misdis[a])
{
misdis[b]=misdis[a]+c;
}
}
}
if(misdis[n]==INT_MAX)
{
cout<<"unconnected";
return 0;
}
cout<<misdis[n];
return 0;
}
单纯遍历n-1次
O(mn);
队列优化

include<bits/stdc++.h>

using namespace std;
int n,m;
struct Edge
{
int to;
int val;
Edge(int x,int y):to(x),val(y){}
};

int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
vector<list>ljb(n+1);
for(int i=0;i<m;i++)
{
int a,b,c;
cin>>a>>b>>c;
ljb[a].push_back(Edge(b,c));
}
vectorinqueue(n+1,false);
queueque;
vectormindis(n+1,INT_MAX);
mindis[1]=0;
que.push(1);
inqueue[1]=1;
while(!que.empty())
{
auto p=que.front();
que.pop();
inqueue[p]=0;
for(Edge edge:ljb[p])
{
int to=edge.to;
int val=edge.val;
if(mindis[to]>mindis[p]+val)
{
mindis[to]=mindis[p]+val;
if(!inqueue[to])
{
inqueue[to]=1;
que.push(to);
}
}
}

}
if(mindis[n]==INT_MAX)
{cout<<"unconnected";return 0;
}
cout<<mindis[n];
return 0;

}
O(m）/平均
O(mn)/最坏（每个节点都和其他点相连）
朴素版+判断负权回路

include<bits/stdc++.h>

using namespace std;
int n,m;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
vector<vector>bian;
for(int i=0;i<m;i++)
{
int a,b,c;
cin>>a>>b>>c;
bian.push_back({a,b,c});
}
vectormisdis(n+1,INT_MAX);
misdis[1]=0;
bool flag=false;//
for(int i=1;i<=n;i++)//ii<=n查是否存在负权回路
{
for(int j=0;j<m;j++)
{
int a=bian[j][0],b=bian[j][1],c=bian[j][2];
if(i<n){
if(misdis[a]!=INT_MAX&&misdis[b]>c+misdis[a])
{
misdis[b]=misdis[a]+c;
}
}
else
{
if(misdis[a]!=INT_MAX&&misdis[b]>c+misdis[a])//还能再小->回路
{
flag=true;
cout<<"circle";
return 0;
}
}
}
}
if(flag1)
{
cout<<"circle";
return 0;
}
if(misdis[n]INT_MAX)
{
cout<<"unconnected";
return 0;
}
cout<<misdis[n];
return 0;
}
队列优化+负权回路判断

include<bits/stdc++.h>

using namespace std;
int n,m;
struct Edge
{
int to;
int val;
Edge(int x,int y):to(x),val(y){}
};

int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
vector<list>ljb(n+1);
for(int i=0;i<m;i++)
{
int a,b,c;
cin>>a>>b>>c;
ljb[a].push_back(Edge(b,c));
}
vectorinqueue(n+1,false);
queueque;
vectormindis(n+1,INT_MAX);
vectorcount(n+1,0);//增加检查加入次数（判断如度）
count[1]++;
mindis[1]=0;
que.push(1);
inqueue[1]=1;
while(!que.empty())
{
auto p=que.front();
que.pop();
inqueue[p]=0;
for(Edge edge:ljb[p])
{
int to=edge.to;
int val=edge.val;
if(mindis[to]>mindis[p]+val)
{
mindis[to]=mindis[p]+val;
if(!inqueue[to])
{
inqueue[to]=1;
que.push(to);
count[to]++;
}
}
if(count[to]==n)//判断
{
cout<<"circle";
return 0;
}
}

}
if(mindis[n]==INT_MAX)
{cout<<"unconnected";return 0;
}
cout<<mindis[n];
return 0;

}