fore_graph.cpp

多段图向前处理程序：可以自己定义多段图的所有内容

 #include <iostream>
using namespace std;

const int k=5;//k段图
const int n=12;//n个节点
const int MAX_E=100;//两点之间最大距离
const int MAX_C=1000;
void fgraph(int e[n+1][n+1])
{
	int COST[n+1];
	int D[n];
	int p[k+1];
	int i,j,r;
	COST[n]=0;
	for(j=n-1;j>=1;j--)
	{   
		int min_cost=MAX_C;
		for(i=n;i>j;i--)
		{	
			if(e[j][i]<MAX_E && e[j][i]+COST[i]<min_cost)
			{
				min_cost=e[j][i]+COST[i];
			    r=i;
			}
		}
		COST[j]=e[j][r]+COST[r];
		D[j]=r;
	}
	p[1]=1;
	p[k]=n;
	for(j=2;j<=k-1;j++)
		p[j]=D[p[j-i]];
	cout<<"多段图最段路径为："<<endl;
	for(j=1;j<=k;j++)
		cout<<p[j]<<"---->";
	cout<<endl;
}

void main()
{
	int e[n+1][n+1];
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			e[i][j]=MAX_E;
	}
	cout<<"输入多段图成本值,若两节点之间没有路径,输入100:"<<endl;
	int a[k+1];
	for(int j=1;j<=k;j++)
	{
		cout<<"第"<<j<<"段图有几个节点:";
		cin>>a[j];
	}
	a[0]=1;
	int l1=0;
	int l2=0;
	int l3;
	int l4;
	for(int m=0;m<=k-2;m++)
	{
        l1=l1+a[m];
		l2=l2+a[m+1];
		l3=l2+1;
		l4=l2+a[m+2];
		for(int m1=l1;m1<=l2;m1++)
		{ 
			for(int m2=l3;m2<=l4;m2++)
			{
				cout<<"("<<m1<<","<<m2<<")=";
		        cin>>e[m1][m2];
			} 
		}
	}
    fgraph(e);
}