如何愉快进行阳光长跑
海胖子 - 2014/04/15杭电校园阳光长跑启用信息采集终端机! 详情戳我!
这能忍?! 正所谓,上有政策,下有对策~
海胖子心系广大校友, 本着为校友谋福利的态度, 为大家寻找长跑最佳路线!
事情还要从这条说说说起:
看吧,就是这么一道题目勾起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 - 海胖博客