本文主要是介绍最短路--bellman-ford--以x为起点和终点的最短路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
bellman-ford，单源最短路算法，即可以以O(VE)内求已知起点到所有点的最短路。
poj3268
有向图，1..n的奶牛出发到x，再回家，求其中路程最长的奶牛的路程。
以x为起点就可以求所有奶牛回家的最短路。
而要求以x为终点的最短路，就将所有边的方向反一反，即可。
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1000 + 5;
const int INF = 1 << 30;
int d[maxn];
int ans[maxn];
struct edge{
int u,v,w;
};
vector<edge> es;
int n,m,x;
void bellman(int s,int dir)
{
for (int i = 1; i <= n ; i ++) {
d[i] = INF;
}
d[s] = 0;
while (true) {
bool fg = false;
for (int i = 0; i < es.size(); i ++) {
edge &e = es[i];
if(!dir){
if(d[e.u] != INF && d[e.u] + e.w < d[e.v])
{ d[e.v] = d[e.u] + e.w;
fg = true;
}
}
else {
if(d[e.v] != INF && d[e.v] + e.w < d[e.u])
{ d[e.u] = d[e.v] + e.w;
fg = true;
}
}
}
if(!fg) break;
}
}
void solve()
{
memset(ans, 0, sizeof(ans));
bellman(x,0);
memcpy(ans + 1, d + 1, sizeof(int) * n);
bellman(x, 1);
for (int i = 1; i <= n; i ++) {
ans[i] += d[i];
}
printf("%d\n",*max_element(ans + 1, ans + 1 + n));
}
int main()
{
scanf("%d%d%d",&n,&m,&x);
int u,v,w;
for (int i = 0; i < m; i ++) {
scanf("%d%d%d",&u,&v,&w);
es.push_back({u,v,w});
}
solve();
return 0;
}
这篇关于最短路--bellman-ford--以x为起点和终点的最短路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
