[cpp]
　　#include<stdio.h>
　　#include<stdlib.h>
　　#include<string.h>
　　#define NIL 100000
　　struct Node
　　{
　　int d;  //记录最短路径长度
　　int m; //记录最小花费
　　int pre; //记录前驱
　　int flag; //标记所属集合
　　}node[1001];
　　/*
　　初始化操作,把源点初始化为0,其他正无穷
　　@param n 结点个数
　　@param s 源点
　　*/
　　int init_shortpath_source(int n, int s)
　　{
　　int i = 1;
　　for(i = 1; i <= n; ++i)
　　{
　　node[i].d = NIL;  //开始置最短路径为正无穷
　　node[i].m = NIL; //最小花费为正无穷
　　node[i].flag = 0; //所属 0 集合
　　node[i].pre = 0; //前驱为 0
　　}
　　node[s].d = 0;  //源点最短路径置为 0
　　node[s].m = 0;//最小花费置为 0
　　return 1;
　　}
　　/*松弛操作
　　*@param u 路径起始点
　　*@param v 路径结束点
　　*@param gp 路径图
　　*@param gm 花费图
　　*/
　　int relax(int u, int v, int** gp, int** gm)
　　{
　　if(node[v].d > node[u].d + gp[u][v]) //对路径进行松弛
　　{
　　node[v].d = node[u].d + gp[u][v];
　　node[v].m = node[u].m + gm[u][v];
　　node[v].pre = u;
　　}
　　else if(node[v].d == node[u].d + gp[u][v]) //对花费进行松弛
　　{
　　if(node[v].m >= node[u].m + gm[u][v])
　　{
　　node[v].d = node[u].d + gp[u][v];
　　node[v].m = node[u].m + gm[u][v];
　　node[v].pre = u;
　　}
　　}
　　return 1;
　　}