1003:
dfs遍历所有路径。
#include <iostream>
#include <vector>
using namespace std;
int city;
int road;
int collect=0;
int maxcollect=0;
int shortnum=0;
int used[501];
int team[501]={0};
int minpass[501]={0};
int shortdis=100000000;
int curdis=0;
int map[501][501]={0};
int S,T;
vector<int> path;
void dfs(int u)
{
if(u==T)
{
for(int i=0;i<path.size();i++)
{
collect+=team[path[i]];
}
for(int i=0;i<path.size()-1;i++)
{
curdis+=map[path[i]][path[i+1]];
}
if(curdis<shortdis)
{
shortnum=1;
shortdis=curdis;
maxcollect=collect;
}
else if(curdis==shortdis)
{
shortnum++;
if(collect>maxcollect)
maxcollect=collect;
}
curdis=0;
collect=0;
}
else
{
for(int v=0;v<501;v++)
if(map[u][v])
{
if(used[v]==false) //avoid loop
{
used[v]=true;
path.push_back(v);
dfs(v);
path.pop_back();
used[v]=false;
}
}
}
}
int main()
{
int x;
int y;
int value;
int i;
int j;
cin>>city;
cin>>road;
cin>>S;
cin>>T;
for(i=0;i<city;i++)
cin>>team[i];
for(i=0;i<road;i++)
{
cin>>x;
cin>>y;
cin>>value;
map[x][y]=value;
map[y][x]=value;
}
path.push_back(S);
used[S] = 1;
dfs(S);
used[S] = 0;
path.pop_back();
printf("%d %d",shortnum,maxcollect);
return 0;
}
分享到:
相关推荐
lora-l101-pAT-demo-V1.0
PAT-Noxim - NoC 模拟器 欢迎使用 PAT-Noxim,循环精确的片上网络 (NoC) 模拟器。 描述 片上网络 (NoC) 已被证明在众核架构中具有低延迟和高度可扩展性。 由于可扩展性的重要性,设计人员尝试优化整个网络的延迟、...
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 ...
generator-pat-marionette generatorGetting Started全局安装 yeoman、grunt-cli、bowernpm install -g yonpm install -g grunt-clinpm install -g bower由于当前generator没有注册到gurnt上去,所以你要先把源文件...
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视频的结构, 有利工具.
当正确选项是 A、B、C、D 时,分别输出 1、2、3、4。输入输出格式输入第一行给出一个正整数 N,随后 N 行,每行按照“编号-答案”的格式给出一道题的 4
pat顶级和leetcode 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...
【CCF CSP-202012-1】期末预测之安全指数题意概述输入输出格式输入的第一行包含一个正整数 n。接下来 n 行,每行包含用空格分隔的两个整数,分别表示
PAT / leetcode 或其他平台。 拍 PAT(Programming algorithm test)是浙江大学创建的一个测试。 它包含三个级别:基本/高级/顶级。 这个存储库主要包括高级级别。 通常,我会在代码头中记录我在每个算法问题中消耗...
题名 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 字符和