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

PAT甲级1003Emergency

时间:2024-10-01 10:18:56浏览次数:17  
标签: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

相关文章

  • 1043 Is It a Binary Search Tree——PAT甲级
    ABinarySearchTree(BST)isrecursivelydefinedasabinarytreewhichhasthefollowingproperties:Theleftsubtreeofanodecontainsonlynodeswithkeyslessthanthenode'skey.Therightsubtreeofanodecontainsonlynodeswithkeysgreater......
  • 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年模式识别与图像分析国际学术会......