首页 > 其他分享 >PAT甲级1003Emergency

PAT甲级1003Emergency

时间:2024-10-01 10:18:56浏览次数:10  
标签:p1 PAT int 1003Emergency num 甲级 kinds line cities

介绍

寻找路径最短的种类数并输出最短路径的最多救援队数量

As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.

Input Specification:

Each input file contains one test case. For each test case, the first line contains 4 positive integers: N (≤500) - the number of cities (and the cities are numbered from 0 to N−1), M - the number of roads, C1​ and C2​ - the cities that you are currently in and that you must save, respectively. The next line contains N integers, where the i-th integer is the number of rescue teams in the i-th city. Then M lines follow, each describes a road with three integers c1​, c2​ and L, which are the pair of cities connected by a road and the length of that road, respectively. It is guaranteed that there exists at least one path from C1​ to C2​.

Output Specification:

For each test case, print in one line two numbers: the number of different shortest paths between C1​ and C2​, and the maximum amount of rescue teams you can possibly gather. All the numbers in a line must be separated by exactly one space, and there is no extra space allowed at the end of a line.

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long  
#define ull unsigned long long
int i,j,n,m;
int num1[1001][1001];
int kinds_num=0;
int kinds=99999;
bool num2[1001];
int where_num[501];
int kinds_amount=-1;
void dfs(int now1,int sum,int num)//sum=road_length num=team
{
    
    if(now1==m)
    {
        //memset(num2,0,sizeof(num2));
        //kinds[sum]++;
        if(sum<kinds)
        {
            kinds=sum;
            kinds_num=1;
            kinds_amount=num;
        }
        else if(sum==kinds)
        {
            kinds_num++;
            kinds_amount=max(kinds_amount,num);
        }
        return;
    }
    num2[now1]=1;
    for(int a1=0;a1<=i-1;a1++)
    {
        if(num2[a1]==0&&num1[now1][a1]!=0)
        {
            num2[a1]=1;
            dfs(a1,sum+num1[now1][a1],num+where_num[a1]);
            num2[a1]=0;
        }
    }
}
void solve() {
	
	memset(num1,0,sizeof(num1));
	memset(num2,0,sizeof(num2));
    //memset(kinds,0,sizeof(kinds));
    //memset(kinds_amount,0,sizeof(kinds_amount));
    cin>>i>>j>>n>>m;
    int p1,p2;
    int i1,j1;

    for(int p1=0;p1<=i-1;p1++)
    {
        cin>>where_num[p1];
    }
    for(int p1=0;p1<=j-1;p1++)
    {
        
        cin>>i1>>j1>>p2;
        num1[i1][j1]=p2;
        num1[j1][i1]=p2;
    }
    dfs(n,0,where_num[n]);
    //int *ssr=lower_bound(kinds,kinds+501,1);
    cout<<kinds_num<<" "<<kinds_amount;
} 

signed main() {

    ll t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

标签:p1,PAT,int,1003Emergency,num,甲级,kinds,line,cities
From: https://blog.csdn.net/song0789/article/details/142624586

相关文章

  • [USACO23JAN] Tractor Paths P 题解
    T4[USACO23JAN]TractorPathsP唯二的两道蓝题之一,但难度至少紫黑之间。思路是这篇题解的。首先一个贪心:跳到与当前区间相连的最靠右的区间肯定是最优的,由此倍增易得第一问。重点在于第二问的求解,我们发现这个东西很麻烦,这时候就需要一些寄巧了。具体来说,前人之述备矣。坑点:D......
  • xpath解析数据
    节点的关系:父子同胞先辈后代常用路径表达式表达式描述nodename选取此节点的所有子节点/从根节点选取//从匹配选择的当前节点中选择文档的节点.获取当前节点..选取当前节点的父节点@选择属性通配符通配符描述*匹配任何元素节点......
  • 1043 Is It a Binary Search Tree——PAT甲级
    ABinarySearchTree(BST)isrecursivelydefinedasabinarytreewhichhasthefollowingproperties:Theleftsubtreeofanodecontainsonlynodeswithkeyslessthanthenode'skey.Therightsubtreeofanodecontainsonlynodeswithkeysgreater......
  • 奖金高达 110 万元,Spatial Joy 2024 全球 AR 应用开发大赛启动
       今年是AR应用开发大赛第三届,恰逢Rokid成立十周年,我们推出全新的大赛品牌“SpatialJoy”,引领开发者享受开发乐趣,为其打造充满挑战和惊喜的开发之旅,逐渐成为空间计算时代全球最大AR应用开发大赛。回顾大赛发展,Rokid于2022年9月第一次发起并主办了AR应用开发大赛,去年的第......
  • 【Python脚本】路径管理之pathlib
    在Python的pathlib模块中,Path类和PurePath类是用于处理文件和目录路径的两个主要类.它们具有不同的目的和功能,以下是它们的主要异同点:类的继承关系:Path类继承自PurePath,因此Path类拥有PurePath的所有方法.不同点:PurePath类:纯路径对象:PurePath类及其子类(如Pure......
  • P9019 [USACO23JAN] Tractor Paths P 题解
    P9019[USACO23JAN]TractorPathsP题解难度其实绝对不止蓝题。先考虑第一问。维护任意两点之间的最短路是困难的,难以dp或是采取其它方法解决。难以算最短路就转换思路,考虑从\(x\)走\(p\)步能走到哪。考虑到这个东西是有单调性的,也就是说对于\(x<y<z\),从\(x\)能走到......
  • `pattern = r“(\d+)(CNY|JPY|HKD|EUR|GBP|fen|cents|sen|eurocents|pence)“
    pattern=r"(\d+)(CNY|JPY|HKD|EUR|GBP|fen|cents|sen|eurocents|pence)"是一个正则表达式,用于匹配特定格式的字符串。正则表达式解析整体结构:r"...":前缀r表示这是一个原始字符串(RawString),在原始字符串中,反斜杠(\)不会被视作转义字符,这样可以更方便地编写正则表达式......
  • maven annotationProcessorPaths
    <plugin><groupId>org.apache.maven.plugins</groupId><artifactId>maven-compiler-plugin</artifactId><version>${maven-compiler-plugin.version}</version><configuration><annotat......
  • export PATH="/opt/homebrew/bin:$PATH" 或者eval "$(/opt/homebrew/bin/brew shellen
    这两种方式都是为了将Homebrew的路径添加到系统的环境变量PATH中,使得可以在终端中使用Homebrew命令,但它们的实现方式和作用略有不同。exportPATH="/opt/homebrew/bin:$PATH":这种方式是直接将Homebrew的安装路径(/opt/homebrew/bin)添加到当前shell会话的PATH变量......
  • 2024年模式识别与图像分析国际学术会议(PRIA 2024) 2024 International Conference on P
    文章目录一、会议详情二、重要信息三、大会介绍四、出席嘉宾五、征稿主题六、咨询一、会议详情二、重要信息大会官网:https://ais.cn/u/vEbMBz提交检索:EICompendex、IEEEXplore、Scopus2024年10月18-20日南京三、大会介绍2024年模式识别与图像分析国际学术会......