HDU 3790 最短路径问题

[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;
}
/*申请二维数组空间，大小为n*n

@param n 二维数组空间的大小
@result 返回一个 (n+1)*(n+1) 大小的二维数组，下标从1开始到n
*/
int** apply_malloc(int n)
{
    int **p;
    int i;
    p = (int**)malloc(sizeof(int)*(n+1));
    for(i = 0; i<=n; ++i)
    {
        p[i] = (int *)malloc(sizeof(int)*(n+1));
    }
    return p;
}

/*初始化二维数组
@param gp 存储路径权值
@param gm 存储花费权值
*/
int init(int **gp, int **gm, int n)
{
    int i = 1,j = 1;
    for(i = 1;i <= n; ++i)
    {
        for(j = i; j <= n; ++j)
        {
            gp[i][j] = NIL;
            gp[j][i] = NIL;
            gm[i][j] = NIL;
            gm[j][i] = NIL;
        }
    }
    return 1;
}

/**
Dijkstra 算法
*/
int dijkstra(int ** gp, int ** gm, int s, int n)
{
    int flag = n;
    int index = 0;
    int i,j,min;
    init_shortpath_source(n,s);
    while(flag--)
    {
        /*查找集合 0 中，路径上界最小的结点*/
        for(i = 1; i <= n; ++i)
        {
            if(node[i].flag == 0)
            {
                min = node[i].d;
                index = i;
                break;
            }
        }
        for(++i; i <= n; ++i)
        {
            if(node[i].flag == 0 && min > node[i].d)
            {
                min = node[i].d;
                index = i;
            }
        }

        /*将该点加入 1 集合*/
        node[index].flag = 1;

        /*对每个以该点为起点的路径进行松弛操作*/
        for(j = 1; j <= n; ++j)
        {
            if(node[j].flag == 0 && gp[index][j] != NIL)
            {
                relax(index,j,gp,gm);
            }
        }
    }
    return 1;
}

/*打印一个二维数组*/
int printf_array_2(int ** array, int n)
{
    int i,j;
    for(i = 1; i <= n; ++i)
    {
        for(j = 1; j <= n; ++j)
        {
            printf("%d\t", array[i][j]);
        }
        printf("\n");
    }&nbs

补充：软件开发 , C++ ,