#include

//#define?LEN?sizeof（struct?NODE）
#define?N?10
#define?MAX_TYPE?10000
#define?ZERO_TYPE?0
/*定義圖的鄰接鏈表*/
struct?NODE?/*鄰接表節點的數據結構*/
{???????????????
int?v_num;/*鄰接頂點的編號*/
int?len;/*鄰接頂點與該頂點的費用*/
struct?NODE?*next;/*下一個鄰接頂點*/
};
NODE?*node=new?NODE[N];?/*多段鄰接鏈表頭節點*/

int?cost[N];/*在多段決策中各個定點到收點的最小費用*/
int?*route=new?int[N];/*從原點到收點的最短路徑上的頂點編號*/
int?path[N];/*在階段決策中，各個頂點到收點的最短路徑上的前方頂點編號*/


int?fgragh（int?n）
{int?i;
struct?NODE?*pnode;
int?*path=new?int[n];
int?min_cost*cost=new?int[n];
for（i=0;i{cost[i]=MAX_TYPE;
path[i]=-1;
route[i]=0;
}
cost[n-1]=ZERO_TYPE;
for（i=n-2;i>=0;i--）
{
pnode=node[i].next;
while（pnode!=NULL）{
if（pnode->len+cost[pnode->v_num]{cost[i]=pnode->len+cost[pnode->v_num];
path[i]=pnode->v_num;
}
pnode=pnode->next;
}
}
i=0;
while（（route[i]!=n-1）&&（path[i]!=-1））
{