大臣的旅费

boyfaceone · 发表于 2013-6-24 23:42:52

很久以前，T王国空前繁荣。为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。

为节省经费，T国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。

J是T国重要大臣，他巡查于各大城市之间，体察民情。所以，从一个城市马不停蹄地到另一个城市成了J最常做的事情。他有一个钱袋，用于存放往来城市间的路费。

聪明的J发现，如果不在某个城市停下来修整，在连续行进过程中，他所花的路费与他已走过的距离有关，在走第x千米到第x+1千米这一千米中（x是整数），他花费的路费是x+10这么多。也就是说走1千米花费11，走2千米要花费23。

J大臣想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？

输入格式：
输入的第一行包含一个整数n，表示包括首都在内的T王国的城市数
城市从1开始依次编号，1号城市为首都。
接下来n-1行，描述T国的高速路（T国的高速路一定是n-1条）
每行三个整数Pi, Qi, Di，表示城市Pi和城市Qi之间有一条高速路，长度为Di千米。

输出格式:
输出一个整数，表示大臣J最多花费的路费是多少。

样例输入:
5
1 2 2
1 3 1
2 4 5
2 5 4

样例输出:
135

样例说明:
大臣J从城市4到城市5要花费135的路费。

资源约定：
峰值内存消耗 < 64M
CPU消耗 < 5000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>，不能通过工程设置而省略常用头文件。

提交时，注意选择所期望的编译器类型。

boyfaceone · 发表于 2013-6-30 00:09:44

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 调试开关
#define _DEBUG_ 0

// 最大顶点个数
#define MAX_VERTEX 32

// 取最大值
#define MAX(a, b) ((a) > (b) ? (a) : (b))

// 检测分配内存是否成功
#define CHECK_MALLOC(p)               \
{                                     \
    if (NULL == p)                    \
    {                                 \
        printf("malloc error.\n");    \
        return -1;                    \
    }                                 \
}

// 邻接点结构定义
typedef struct EdgeNode
{
    int adjVex;              // 邻接点在顶点表中的下标
    int weight;              // 权值，这里指距离
    
    struct EdgeNode *next;   // 下一个邻接点
}EdgeNode;

// 顶点表结点定义
typedef struct
{
    int index;               // 城市编号
    EdgeNode *firstEdge;     // 第一个邻接点
}AdjList[MAX_VERTEX];

// 邻接表结构定义
typedef struct
{
    int vertexNum;            // 顶点数
    int edgeNum;              // 边数
    AdjList adjList;          // 邻接表
}GraphAdjList;

// -------------------------------------------------------------------------
// - 函数名: initAdjList
// - 功能描述: 初始化邻接表
// - 输入参数: vertexNum:顶点个数；edgeNum:边数
// - 输出参数: graph:邻接图
// - 返回值: void
// - 备    注:
// -------------------------------------------------------------------------
void initAdjList(GraphAdjList *graph, int vertexNum, int edgeNum)
{
    int i;
    
    memset(graph, 0, sizeof(GraphAdjList));
    
    graph->vertexNum = vertexNum;
    graph->edgeNum = edgeNum;
    
    for (i = 0; i < graph->vertexNum; i++)
    {
        graph->adjList.index = i;
        graph->adjList.firstEdge = NULL;
    }
}

// -------------------------------------------------------------------------
// - 函数名: createAdjList
// - 功能描述: 创建邻接表
// - 输入参数: 无
// - 输出参数: graph:邻接图
// - 返回值: 0:成功；其他:失败
// - 备    注:
// -------------------------------------------------------------------------
int createAdjList(GraphAdjList *graph)
{
    int i;                          // 循环变量
    int from;                       // 起始城市编号
    int to;                         // 目标城市编号
    int distance;                   // 两城市间距离
    EdgeNode *pEdgeNode = NULL;
    
    for (i = 0; i < graph->edgeNum; i++)
    {
        // 从标准输入获取高速公路信息
        fflush(stdin);
        scanf("%d %d %d", &from, &to, &distance);

        // 将高速公路信息加入邻接表
        pEdgeNode = (EdgeNode*)malloc(sizeof(EdgeNode));
        CHECK_MALLOC(pEdgeNode);
        pEdgeNode->adjVex = to - 1;
        pEdgeNode->weight = distance;
        pEdgeNode->next = graph->adjList[from-1].firstEdge;
        graph->adjList[from-1].firstEdge = pEdgeNode;
        
        pEdgeNode = (EdgeNode*)malloc(sizeof(EdgeNode));
        CHECK_MALLOC(pEdgeNode);
        pEdgeNode->adjVex = from - 1;
        pEdgeNode->weight = distance;
        pEdgeNode->next = graph->adjList[to-1].firstEdge;
        graph->adjList[to-1].firstEdge = pEdgeNode;
    }
    
    return 0;
}

#if _DEBUG_
// -------------------------------------------------------------------------
// - 函数名: printGraphAdjList
// - 功能描述: 打印邻接表
// - 输入参数: graph:邻接表指针
// - 输出参数: 无
// - 返回值: void
// - 备    注: 调试使用，格式为:"[城市编号]: ->(相邻城市编号，距离)"
// -------------------------------------------------------------------------
void printGraphAdjList(const GraphAdjList *graph)
{
    int i;
    EdgeNode *pEdgeNode = NULL;
    
    puts("=========================");
    for (i = 0; i < graph->vertexNum; i++)
    {
        printf("[%d]: ", graph->adjList.index);
        
        pEdgeNode = graph->adjList.firstEdge;
        while (NULL != pEdgeNode)
        {
            printf("->(%d,%d)", pEdgeNode->adjVex + 1, pEdgeNode->weight + 1);
            pEdgeNode = pEdgeNode->next;
        }
        
        printf("\n");
    }
    puts("=========================");
}
#endif

// -------------------------------------------------------------------------
// - 函数名: dfs
// - 功能描述: 深度优先遍历邻接图
// - 输入参数: graph:邻接图指针；vertex1:起始城市编号；vertex2:目标城市编号
// - 输出参数: distance:两城市之间距离；visit:访问标记
// - 返回值: 0:成功；1:失败
// - 备    注:
// -------------------------------------------------------------------------
int dfs(GraphAdjList *graph, int vertex1, int vertex2, int *distance, int visit[])
{
    EdgeNode *pEdgeNode = NULL;

    // 之前已经访问过，回退
    if (0 != visit[vertex1])
    {
        return 1;
    }

    // 打访问标记
    visit[vertex1] = 1;

    // 找到目标城市，返回成功
    if (graph->adjList[vertex1].index == vertex2)
    {
        return 0;
    }

    // 遍历当前城市的所有邻接城市
    pEdgeNode = graph->adjList[vertex1].firstEdge;
    while (NULL != pEdgeNode)
    {
        // 没访问过则访问
        if (0 == visit[pEdgeNode->adjVex])
        {
            // 加上与当前城市之间的距离
            *distance += pEdgeNode->weight;

            // 递归访问城市
            if (0 == dfs(graph, pEdgeNode->adjVex, vertex2, distance, visit))
            {
                return 0;
            }
        }

        pEdgeNode = pEdgeNode->next;
    }

    // 在当前城市的所有邻接城市中均未找到目标城市，减去距离，回退
    *distance -= graph->adjList[vertex1].firstEdge->weight;

    return 1;
}

// -------------------------------------------------------------------------
// - 函数名: getDistance
// - 功能描述: 获取两城市之间的距离
// - 输入参数: graph:邻接图；vertex1:城市1下标；vertex2:城市2下标
// - 输出参数: 无
// - 返回值: int 两城市之间的距离
// - 备    注:
// -------------------------------------------------------------------------
int getDistance(GraphAdjList *graph, int vertex1, int vertex2)
{
    int distance = 0;                 // 城市距离
    int visited[MAX_VERTEX] = {0};    // 访问标记

    (void)dfs(graph, vertex1, vertex2, &distance, visited);

    return distance;
}

// -------------------------------------------------------------------------
// - 函数名: getMaxDistance
// - 功能描述: 获取图中最远的两座城市之间的距离
// - 输入参数: graph:邻接图
// - 输出参数: 无
// - 返回值: int 最大距离
// - 备    注:
// -------------------------------------------------------------------------
int getMaxDistance(GraphAdjList *graph)
{
    int maxDistance = 0;
    int tmpDistance;
    int i, j;

    // 计算各对城市之间的距离，取最大值
    for (i = 0; i < graph->vertexNum; i++)
    {
        for (j = i + 1; j < graph->vertexNum; j++)
        {
            tmpDistance = getDistance(graph, i, j);

#if _DEBUG_
            printf("(%d,%d): %d\n", i + 1, j + 1, tmpDistance);
#endif

            maxDistance = MAX(tmpDistance, maxDistance);
        }
    }

    return maxDistance;
}

// -------------------------------------------------------------------------
// - 函数名: calcFee
// - 功能描述: 根据距离计算路费
// - 输入参数: distance:距离
// - 输出参数: 无
// - 返回值: int:路费
// - 备    注:
// -------------------------------------------------------------------------
int calcFee(int distance)
{
    return (10 * distance + distance * (distance + 1) / 2);
}

int main()
{
    int cityNum;               // 城市数
    int maxDistance = 0;       // 城市间最大距离
    GraphAdjList graph;        // 邻接图

    scanf("%d", &cityNum);
    
    // 初始化邻接表
    initAdjList(&graph, cityNum, cityNum - 1);
    
    // 建立边表
    if (0 != createAdjList(&graph))
    {
        printf("create graph failed.\n");
        return -1;
    }

#if _DEBUG_
    // 打印邻接表
    printGraphAdjList(&graph);
#endif

    // 遍历邻接表寻找最远的两座城市
    maxDistance = getMaxDistance(&graph);

    // 计算并打印最多的路费
    printf("%d\n", calcFee(maxDistance));
    
    return 0;
}

那个谁 · 发表于 2013-6-30 10:28:03

boyfaceone:#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 调试开关
....... (2013-06-30 00:09)

狂赞啊。。。

		自动登录	找回密码
密码			立即注册

大臣的旅费

回 boyfaceone 的帖子

浏览过的版块