链接:http://pat.zju.edu.cn/contests/pat-a-practise/1018
题意(转biaobiaoqi):以杭州的公用自行车站点管理为背景。每个站点是一个节点,每个节点上最多停放 Cmax 辆自行车,Cmax/2 为节点的最佳状态。不同节点间距离不同,整个构成了一张带权无向图。要求从起始点(公用自行车管理中心)出发,去目的地维护目的地节点的车辆状态,如果车辆低于 Cmax/2,则给它添加车辆到 Cmax/2 辆,如果多于 Cmax/2,则去除掉几辆车。同时,在去往目的地的过程中,也需要调整所有沿途站点的车辆(这里题目没有交代清楚,实际测试是只能在去往目的地的途中调整,回来的途上不可调整)。求到给定目的地的最短路径,如果有多条最短路径,则按照 1.从管理中心送出的车辆越少越好;2.拿回到管理中心的车越少越好的优先级找到结果。
分析:首先利用dijkstra算法求出最短路径的长度,然后dfs求出所有的最短路径,然后在其中寻找题目要求的最优的路径。
#include<stdio.h> #include<vector> using namespace std; #define Inf 100000000 int c, n, sp, m; int bikeNum[505]; int mat[505][505]; int found[505]; int d[505]; int p[505]; int visited[505]; vector<vector<int> > shortestPaths; int getMinIdx() { int i; int minDis = Inf; int minIdx = -1; for (i = 0; i <= n; i++) { if (!found[i] && d[i] < minDis) { minDis = d[i]; minIdx = i; } } return minIdx; } void dfs(int v, int dis, int num, vector<int>& vec) { vec.push_back(v); if (dis > d[sp]) { vec.pop_back(); return; } if (v == sp && dis == d[sp]) { shortestPaths.push_back(vec); vec.pop_back(); return; } visited[v] = 1; int i; for (i = 0; i <= n; i++) { if (!visited[i] && mat[v][i]) dfs(i, dis + mat[v][i], num + bikeNum[v] - c / 2, vec); } visited[v] = 0; vec.pop_back(); return; } int main() { // freopen("in.txt", "r", stdin); scanf("%d%d%d%d", &c, &n, &sp, &m); int i; for (i = 1; i <= n; i++) scanf("%d", &bikeNum[i]); int from, to, dis; for (i = 0; i < m; i++) { scanf("%d%d%d", &from, &to, &dis); mat[from][to] = dis; mat[to][from] = dis; } d[0] = 0; for (i = 1; i <= n; i++) d[i] = Inf; for (i = 0; i <= n; i++) p[i] = -1; int idx; do { idx = getMinIdx(); found[idx] = 1; int i; for (i = 0; i <= n; i++) { if (mat[idx][i] && !found[i]) if (d[i] > d[idx] + mat[idx][i]) { d[i] = d[idx] + mat[idx][i]; p[i] = idx; } } } while (idx != sp); vector<int> path; dfs(0, 0, 0, path); int j; int minSendBikeNum = Inf; int minBikeBackNum = Inf; int sendBikeNum[10000]; int bikeBackNum[10000]; for (i = 0; i < shortestPaths.size(); i++) { int sum = 0; int minNum = Inf; int tmpSum = 0; for (j = 0; j < shortestPaths[i].size(); j++) { sum += bikeNum[shortestPaths[i][j]]; if (j) { tmpSum += bikeNum[shortestPaths[i][j]] - c / 2; if (tmpSum < minNum) { minNum = tmpSum; } } } // printf("minNum:%d\n", minNum); int tmp = (shortestPaths[i].size() - 1) * c / 2 - sum; if (tmp >= 0) { sendBikeNum[i] = tmp; bikeBackNum[i] = 0; } else { sendBikeNum[i] = 0; bikeBackNum[i] = -tmp; } if (minNum < 0) { sendBikeNum[i] = -minNum; bikeBackNum[i] = -tmp-minNum; } } for (i = 0; i < shortestPaths.size(); i++) { if (sendBikeNum[i] < minSendBikeNum) { minSendBikeNum = sendBikeNum[i]; } } int resultIdx = -1; for (i = 0; i < shortestPaths.size(); i++) { if (sendBikeNum[i] == minSendBikeNum) { if (bikeBackNum[i] < minBikeBackNum) { minBikeBackNum = bikeBackNum[i]; resultIdx = i; } } } printf("%d ", sendBikeNum[resultIdx]); for (i = 0; i < shortestPaths[resultIdx].size(); i++) { if (i != 0) printf("->"); printf("%d", shortestPaths[resultIdx][i]); } printf(" %d\n", bikeBackNum[resultIdx]); return 0; }
相关推荐
CAD填充图案(三百多种)-.pat文件 部分如下(篇幅有限) 2x12木地板.pat 45度人字形砖面(1).pat 8x8无缝砖.pat Z形砖.pat 丁字砖面1.pat 丁字砖面2.pat 三联蜂窝.pat 三角形拼铺.pat 不能通行的沼泽地.pat 乱沙.pat...
pat1.cpp
标题“pat1.rar_in”可能指的是一个包含图像处理补丁的压缩文件,而“in”标签可能是对内容的简要分类或关键词。压缩文件中的唯一子文件“pat1.m”很可能是一个MATLAB脚本,因为.m文件是MATLAB的源代码文件格式。...
Neural Networks and Deep Learni - Pat Nakamoto.azw3
算法与数据结构它们分别涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)...
5. **pat1018.cpp**:可能是线性数据结构(数组、链表)的操作,如插入、删除、查找等,也可能涉及到栈或队列的应用。 6. **pat1021.cpp**:这题可能与递归或回溯法有关,常见于解决组合问题、迷宫问题、八皇后问题...
dcu2pat.exe I:\delphi.trash\2007\lib\*.dcu wc -l .pat 26959 .pat \ida\flair\bin\sigmake.exe .pat d2007.sig : modules/leaves: 11149849/26655, COLLISIONS: 19389 After resolving of collisions (see ...
Paragon Alignment Tool_PAT.3.0.13045 内置激活码、中文版使用说明(PDF文档,工具安装后是英文界面,可参照中文版使用说明); 工具可用于SSD固态硬盘、机械硬盘、U盘、SD卡/TF卡等移动存储设备4K对齐,支持无损...
是由新加坡国立大学开发的一款形式化建模与验证工具集,支持进程代数、实时进程代数、时间自动机等多种建模语言...PAT工具的人机交互界面友好,支持多种验证方法,包括精化验证、死锁验证、可达性验证、LTL性质验证等。
标题中的“acwing, leetcode, kickstart, 算法模板, PAT 等等.zip”表明这是一个包含多个算法训练平台资源的压缩文件。这些平台都是程序员提升算法能力、准备编程竞赛的重要工具。让我们逐一深入探讨它们以及可能...
把acadiso.pat放到c:\Documents and Settings\当前用户名\Application Data\Autodesk\AUTOCAD 2009\R17.2\CHS\SUPPORT 文件下 适合各中版本的CAD
黑群晖最经典的版本 DSM_DS918+_24922.pat
适合在打基础的同学可以比较深入提前了解比较真实的做题情况,减少焦虑(无解压密码,解压后获得TXT文件)
1009. 说反话 (20) 给定一句英语,要求你编写程序,将句中所有单词的顺序颠倒输出。 输入格式:测试输入包含一个测试用例,在一行内给出总长度不超过80的字符串。字符串由若干单词和若干空格组成,其中单词是由...
根据给定的信息,本文将详细解释TS(Transport Stream)包解析中的关键概念,包括TS头、PAT(Program Association Table)、PMT(Program Map Table)以及PES(Packetized Elementary Stream)。这些是MPEG-2传输流...
MIS(Management Information System,管理信息系统)是现代企业信息化管理的重要工具,它整合了数据处理、业务流程与决策支持等功能,为企业提供高效的信息服务。PAT项目中的MIS管理系统,特别针对客户管理进行了...
patb工程文件的说明文档,对patb工程文件的说明。adj、image、ori、cont。
标题 "patb.rar_enjoy3b8_newton_newton-raphson_数学计算_非线性有限元" 涉及的主题是使用Newton-Raphson方法解决一维非线性问题,具体应用在有限元分析中。Newton-Raphson方法是一种强大的数值迭代技术,常用于...
### 配置PAT知识点详解 #### 一、PAT(Port Address Translation)概念解析 PAT(端口地址转换),是NAT(Network Address Translation)的一种特殊形式,主要用于将一个内部网络中的多个私有IP地址映射到一个或...
安全认证 《2020网络安全人才发展白皮书》 - pat考试 安全管理 安全管理 WEB应用防火墙 金融安全 无线安全