寒假刷题记录,第一天(重刷题目)
2024-01-07 21:55:03
PTA甲级:
1003 Emergency
经典迪杰斯特拉算法
#include<iostream>
#include<cstring>
using namespace std;
const int N = 510 , INF = 0x3f3f3f3f;
int dist[N] , cnt[N] , g[N][N];
int helper[N] , way[N];
bool st[N];
int n , m , c1 , c2;
int main()
{
cin >> n >> m >> c1 >> c2;
for(int i = 0;i < n;i ++)
cin >> cnt[i];
memset(dist , 0x3f , sizeof dist);
memset(g , 0x3f , sizeof g);
while(m --)
{
int a , b , c;
cin >> a >> b >> c;
g[a][b] = g[b][a] = c;
}
dist[c1] = 0 , way[c1] = 1 , helper[c1] = cnt[c1];
for(int i = 0;i < n;i ++)
{
int t = -1;
for(int j = 0;j < n;j ++)
if(!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
st[t] = true;
for(int j = 0;j < n;j ++)
{
if(dist[j] > dist[t] + g[t][j])
{
dist[j] = dist[t] + g[t][j];
way[j] = way[t];
helper[j] = helper[t] + cnt[j];
}
else if(dist[j] == dist[t] + g[t][j])
{
way[j] += way[t];
helper[j] = max(helper[t] + cnt[j] , helper[j]);
}
}
}
cout << way[c2] << " " << helper[c2] << endl;
return 0;
}
1004 Counting Leaves
经典深度优先方法dfs
#include<iostream>
#include<vector>
using namespace std;
const int N = 200;
int n , m;
vector<int>v[N];
int cnt[N];
int dep = 1;
void dfs(int x , int depth)
{
dep = max(dep , depth);
if(!v[x].size())
{
cnt[depth] ++;
return ;
}
for(auto i : v[x])
dfs(i , depth + 1);
}
int main()
{
while(cin >> n)
{
if(!n) break;
cin >> m;
for(int i = 0;i < m;i ++)
{
int id;
cin >> id;
int k;
cin >> k;
while(k --)
{
int id1;
cin >> id1;
v[id].push_back(id1);
}
}
dfs(1 , 1);
for(int i = 1;i <= dep;i ++)
if(i == 1) cout << cnt[i];
else cout << " " << cnt[i];
cout << endl;
}
return 0;
}
天梯赛:
L2-001 紧急救援
同1003一样
L2-048 寻宝图
经典dfs
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int N = 1e5 + 10;
int n , m;
int total , tre;
vector<int>nodes[N];
vector<bool>st[N];
int dx[4] = {0 , 0 , 1 , -1};
int dy[4] = {1 , -1 , 0 , 0};
void dfs(int x , int y , bool &f)
{
if(nodes[x][y] > 1) f = true;
st[x][y] = true;
for(int i = 0;i < 4;i ++)
{
int tx = x + dx[i] , ty = y + dy[i];
if(tx < 0 || tx >= n || ty < 0 || ty >= m) continue;
if(st[tx][ty] || !nodes[tx][ty]) continue;
dfs(tx , ty , f);
}
}
int main()
{
cin >> n >> m;
for(int i = 0;i < n;i ++)
{
string s;
cin >> s;
for(int j = 0;j < m;j ++)
nodes[i].push_back(s[j] - '0') , st[i].push_back(false);
}
for(int i = 0;i < n;i ++)
{
for(int j = 0;j < m;j ++)
{
if(nodes[i][j] && !st[i][j])
{
bool f = false;
dfs(i , j , f);
if(f) tre ++;
total ++;
}
}
}
cout << total << " " << tre << endl;
return 0;
}
文章来源:https://blog.csdn.net/xp_xht123/article/details/135441891
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!