海胖博客

杭电校园阳光长跑启用信息采集终端机！ 详情戳我！

这能忍？！ 正所谓，上有政策，下有对策~

海胖子心系广大校友， 本着为校友谋福利的态度， 为大家寻找长跑最佳路线！

事情还要从这条说说说起：

看吧，就是这么一道题目勾起ACMer欲望~ 于是我很愉快地敲起了代码！ 代码如下： 

    /*
    * Author: Haipz
    * School: HDU
    * File Name: howtorun.cpp
    */
    #include <cstdio>
    #include <cmath>
    #include <ctime>
    #include <cctype>
    #include <cfloat>
    #include <cstdlib>
    #include <cstring>
    #include <climits>
    #include <iostream>
    #include <vector>
    #include <string>
    #include <stack>
    #include <queue>
    #include <set>
    #include <map>
    #include <algorithm>
    using namespace std;
    int N, GirlMin, BoyMin;
    int dis[10][10], ans[1000];
    int StartPoint, EndPoint;
    void CalcDis(int i, int sum, int &Ans, int Min) {
    if (sum >= Min) {
    if (sum < Ans) Ans = sum;
    return;
    }
    int pre = (i + N - 1) % N, next = (i + 1) % N;
    CalcDis(pre, sum + dis[i][pre], Ans, Min);
    CalcDis(next, sum + dis[i][next], Ans, Min);
    return;
    }
    void FindWay(int i, int sum, int top, int Ans) {
    if (sum > Ans) return;
    ans[top] = i;
    if (sum == Ans) {
    for (int j = 0; j < top; ++j) printf("%d -> ", ans[j] + 1);
    printf("%d\n", ans[top] + 1);
    }
    int pre = (i + N - 1) % N, next = (i + 1) % N;
    FindWay(pre, sum + dis[i][pre], top + 1, Ans);
    FindWay(next, sum + dis[i][next], top + 1, Ans);
    return;
    }
    void CalcDisToEnd(int i, int sum, int &Ans, int Min, int j) {
    if (sum >= Min) {
    if (sum < Ans && i == j) Ans = sum;
    return;
    }
    int pre = (i + N - 1) % N, next = (i + 1) % N;
    CalcDisToEnd(pre, sum + dis[i][pre], Ans, Min, j);
    CalcDisToEnd(next, sum + dis[i][next], Ans, Min, j);
    return;
    }
    void FindWayToEnd(int i, int sum, int top, int Ans, int j) {
    if (sum > Ans) return;
    ans[top] = i;
    if (sum == Ans && i == j) {
    for (int k = 0; k < top; ++k) printf("%d -> ", ans[k] + 1);
    printf("%d\n", ans[top] + 1);
    }
    int pre = (i + N - 1) % N, next = (i + 1) % N;
    FindWayToEnd(pre, sum + dis[i][pre], top + 1, Ans, j);
    FindWayToEnd(next, sum + dis[i][next], top + 1, Ans, j);
    return;
    }
    int main() {
    printf("N( <= 10 ): ");
    scanf("%d", &N);
    printf("Dis( %d Numbers ): ", N);
    memset(dis, 0, sizeof(dis));
    for (int i = 0; i < N; ++i) {
    int t;
    scanf("%d", &t);
    dis[i][(i + 1) % N] = dis[(i + 1) % N][i] = t;
    }
    printf("GirlMin: ");
    scanf("%d", &GirlMin);
    printf("BoyMin: ");
    scanf("%d", &BoyMin);
    printf("<---------------------------->\n");
    for (int i = 0; i < N; ++i) {
    printf("Start at point %d:\n", i + 1);
    int GirlAns = INT_MAX, BoyAns = INT_MAX;
    CalcDis(i, 0, GirlAns, GirlMin);
    CalcDis(i, 0, BoyAns, BoyMin);
    printf("Girl: %d m\n", GirlAns);
    FindWay(i, 0, 0, GirlAns);
    printf("Boy: %d m\n", BoyAns);
    FindWay(i, 0, 0, BoyAns);
    printf("<---------------------------->\n");
    }
    while (true) {
    printf("Input 0 to exit.\n");
    printf("Start point( >= 1 && <= %d ): ", N);
    scanf("%d", &StartPoint);
    if (!StartPoint) return 0;
    printf("End point( >= 1 && <= %d ): ", N);
    scanf("%d", &EndPoint);
    if (!EndPoint) return 0;
    --StartPoint, --EndPoint;
    int GirlAns = INT_MAX, BoyAns = INT_MAX;
    CalcDisToEnd(StartPoint, 0, GirlAns, GirlMin, EndPoint);
    CalcDisToEnd(StartPoint, 0, BoyAns, BoyMin, EndPoint);
    printf("Girl: %d m\n", GirlAns);
    FindWayToEnd(StartPoint, 0, 0, GirlAns, EndPoint);
    printf("Boy: %d m\n", BoyAns);
    FindWayToEnd(StartPoint, 0, 0, BoyAns, EndPoint);
    printf("<---------------------------->\n");
    }
    return 0;
    }

代码支持寻找自定义起点到终点的最佳路径！

使用方法如下图：

图片太小看不清楚？右键在新标签页中打开！

点击下载EXE文件：howtorun

转载保留版权：http://haipz.com/blog/i/1245 - 海胖博客