admin管理员组文章数量:1577501
PAT 1003
代码
#include<iostream>
#include <string>
#include<map>
#include<algorithm>
using namespace std;
int n, m, c1, c2;
int roads[510][510], weight[510];
bool mark[510];
const int inf = 99999999;
int mindis=inf;
int maxhands=0;
int mindis_num=0;
void dfs(int cur, int dis,int hands) //cur-当前所在城市编号,dis-当前已走过的路径
{
// cout<<"current city:"<<cur<<endl;
if(dis > mindis) return; //若当前路径已比之前找到的最短路大,没必要继续尝试(一个小优化,可以不写)
if(cur == c2) //当前已到达目的城市,更新min
{
if(dis==mindis)
{
mindis_num+=1;
if(hands>maxhands){
maxhands=hands;
}
}
if(dis < mindis)
{
mindis = dis;
maxhands = hands;
mindis_num=1;
}
return;
}
for(int i = 1; i < n; i++) //对1~n号城市依次尝试
{
if(roads[cur][i] != inf && mark[i] == 0) //若cur与i可达,且i没有在已走过的路径中
{
mark[i] = 1; //标记i为已在路径中
dfs(i, dis+roads[cur][i],hands+weight[i]); //继续搜索
mark[i] = 0; //对从i出发的路径探索完毕,取消标记
}
}
}
int main(){
scanf("%d%d%d%d", &n, &m, &c1, &c2);
for(int i = 0; i < n; i++)
scanf("%d", &weight[i]);
// 数据量大的情况,用scanf快
fill(roads[0], roads[0] + 510 * 510, inf);
fill(mark, mark + 510, 0);
mark[c1]=1;
int a, b, c;
for(int i = 0; i < m; i++) {
scanf("%d%d%d", &a, &b, &c);
roads[a][b] = roads[b][a] = c;
}
dfs(c1,0,weight[c1]);
cout<<mindis_num<<" "<<maxhands;
return 0;
}
解题思路
理解深度优先搜索,最好自己背一套自己会用的dfs,bfs等的模板,方便考试的时候直接套用
对于不同问题,dfs模板需要变形,如本问题需要增加权值(能找到的搜救队数量),那么就在dfs对数据处理的位置进行修改。
测试点问题
无
版权声明:本文标题:PAT 1003 Emergency满分 测试点问题记录 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dianzi/1727822461a1131884.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论