最后一个case还过不了 ==
为什么呢
思路dfs遍历到目标的所有路径
找最短,运送最少,带回最少的路径
#include <iostream>
#include <vector>
#include<memory.h>
using namespace std;
#define MAXV 501
#define INFINITE 1000000000
int mindis = INFINITE;
int mincarry = INFINITE;
int minback;
vector<int> minpath;
int status[MAXV];
int use[MAXV];
int map[MAXV][MAXV];
vector<int> path;
int curdis = 0;
int capacity;
int station;
int target;
int road;
void dfs(int node,int target)
{
if(node == target)
{
for(int i = 0; i < path.size()-1 ; i++)
curdis += map[path[i]][path[i+1]];
int tmpstatus[MAXV];
memset(tmpstatus,0,sizeof(tmpstatus));
for(int i = 0;i<path.size();i++)
tmpstatus[path[i]] = status[path[i]] - capacity/2;
int carry = 0;
int collect = 0; //collect from path
int tmp;
if(curdis <= mindis)
{
for(int i = 1 ;i <= station ;i++)
{
tmp = collect + tmpstatus[i];
if(tmp < 0)
{
carry -= tmp;
collect = 0;
}
else if(tmp >= 0)
{
collect = tmp;
}
}
}
if(curdis < mindis)
{
mindis = curdis;
mincarry = carry;
minback = collect;
minpath = path;
}
else if(curdis == mindis)
{
if(carry < mincarry )
{
mincarry = carry;
minback = collect;
minpath = path;
}
else if(carry == mincarry && collect < minback)
{
minback = collect;
minpath = path;
}
}
curdis = 0;
}
else
{
//all the node that current node can reach
for(int v=0;v<MAXV;v++)
if(map[node][v])
{
if(use[v]==false) //avoid loop
{
path.push_back(v);
use[v] = 1;
dfs(v,target);
use[v] = 0;
path.pop_back();
}
}
}
}
int main()
{
int x,y;
int time;
cin>>capacity>>station>>target>>road;
memset(status,0,sizeof(status));
for(int i = 1 ; i <= station ; i++)
cin>>status[i];
memset(map,0,sizeof(map));
for(int i = 0; i < road ; i++)
{
cin>>x>>y>>time;
map[x][y] = time;
map[y][x] = time;
}
path.push_back(0);
use[0] = 1;
dfs(0,target);
use[0] = 0;
path.pop_back();
cout<<mincarry<<" ";
for(int i = 0 ;i<minpath.size();i++)
{
cout<<minpath[i];
if(i != minpath.size() -1 )
cout<<"->";
}
cout<<" "<<minback<<endl;
}
分享到:
相关推荐
lora-l101-pAT-demo-V1.0
PAT-Noxim - NoC 模拟器 欢迎使用 PAT-Noxim,循环精确的片上网络 (NoC) 模拟器。 描述 片上网络 (NoC) 已被证明在众核架构中具有低延迟和高度可扩展性。 由于可扩展性的重要性,设计人员尝试优化整个网络的延迟、...
generator-pat-marionette generatorGetting Started全局安装 yeoman、grunt-cli、bowernpm install -g yonpm install -g grunt-clinpm install -g bower由于当前generator没有注册到gurnt上去,所以你要先把源文件...
dcu2pat,make Delphi .dcu to .pat!! http://redplait.blogspot.com/2013/05/dcu2pat.html I wrote today some simple hack tool for creating signatures from delphi .dcu files for IDA flair The main idea is ...
vs2010写的代码 语言c++ 1001 害死人不偿命的(3n+1)猜想 使用if语句和while语句
PAT-B1012.数字分类题目描述:给定一系列正整数,请按照要求对数字进行分类,并输出以下五类数字:A1 = 能被5整除的数字中所有偶数的和;每个测试用例先给
【PAT-B1012】数字分类——c++满分题解(csdn)————程序
【PAT-B1063 谱半径——c++满分题解】(csdn)————程序
浙江大学Programming Ability Test《数据结构学习与实验指导》实验项目集里面30道题左右的答案。 网址http://pat.zju.edu.cn/ 做PAT里面的题时,我自己写得代码。
浙江大学PAT题解(C/C++/Java/Python) - 努力成为萌萌的程序媛
textarea class =“ pat-tinymce” data-pat-tinymce =“ inline:false”>这是tinymce的非内联/ iframe实例。 </ textarea> < textarea class =" pat-tinymce " data-pat-tinymce =" inline: false " &...
主控为STM32F103,wifi模组由涂鸦提供,wifi为透传模式,stm32为主控,搭配电机,DHT11温湿度模块,触摸屏。
ts解析器, 分析ts视频的结构, 有利工具.
PAT-Basic-Level 个人准备的PAT乙级考试 不定期更新,用空就来刷刷题。。。 更新日志: 时间 题目 17.5.9 1026.cpp 1046.cpp 17.5.13 1004.cpp 1018.cpp 1041.cpp 1032.cpp 17.5.14 1036.cpp 1027.cpp 1012.cpp 1028...
拍拍和leetcode 介绍 该存储库存储算法实践的代码,如 PAT / leetcode 或其他平台。 拍 PAT(Programming ...通常,我会在代码头中记录我在每个算法问题中消耗的日期和时间。 它有助于提高我的效率。
当正确选项是 A、B、C、D 时,分别输出 1、2、3、4。输入输出格式输入第一行给出一个正整数 N,随后 N 行,每行按照“编号-答案”的格式给出一道题的 4
【CCF CSP-202012-1】期末预测之安全指数题意概述输入输出格式输入的第一行包含一个正整数 n。接下来 n 行,每行包含用空格分隔的两个整数,分别表示
Paton - Fundamentals of Digital Electronics
题名 Hands-On RESTful API Design Patterns and Best Practices 副标题 Design, Develop, and Deploy Highly Adaptable, Scalable, and Secure RESTful Web APIs 作者 Harihara Subramanian and Pethuru Raj ...
题意概述给定两个字符串 A 和 B,本题要求你输出 A+B,即两个字符串的并集。数据规模A 和 B 均为长度不超过${10}^6$的、由可见 ASCII 字符和