Bellman有向图
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<deque>
#include<iostream>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=100;
struct edge{
int head;
int tail;
int cost;
}edge[N];
int graph[N][N];
int check[N];
int dis[N];
int n,m;
void Bellman(int m)
{
int i,p,j;
int check;
for(i=0;i<n;i++)
dis[i]=(i==0?0:INF);
for(i=1;i<=n-1;i++)
{
check=0;
for(j=1;j<=m;j++)
if(dis[edge[j].tail]>dis[edge[j].head]+edge[j].cost)
{
dis[edge[j].tail]=dis[edge[j].head]+edge[j].cost;
check=1;
}
if(check==0)
break;
}
/*此处应添加判断负权环的代码*/
/*此处应添加判断负权环的代码*/
/*此处应添加判断负权环的代码*/
/*此处应添加判断负权环的代码*/
}
int main()
{
int i,p,j;
int a,b,c;
scanf("%d",&n);
i=0;
while(1)
{
i++;
scanf("%d%d%d",&edge[i].head,&edge[i].tail,&edge[i].cost);
if(edge[i].head==-1&&edge[i].tail==-1&&edge[i].cost==-1)
break;
}
i--;
Bellman(i);
for(i=1;i<n;i++)
printf("%d\n",dis[i]);
return 0;
}
| 
转播
