社区讨论
dfs求大佬看一眼呜呜呜
P1396营救参与者 4已保存回复 7
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 7 条
- 当前快照
- 1 份
- 快照标识符
- @lo327kqp
- 此快照首次捕获于
- 2023/10/23 23:35 2 年前
- 此快照最后确认于
- 2023/10/23 23:35 2 年前
原解是用的二分答案
dfs会超时,但是我想把正确dfs做法写出来
但是好像有几个点还是WA不是TLE
CPP#include <iostream>
using namespace std;
int total_area;
int total_road;
int start, target;
int degree[(int)1e4 + 100][(int)1e4 + 100];
int min_degree = 1000000000;
int degree_now;
void dfs(int start_point)
{
if (start_point == target)
{
min_degree = min(min_degree, degree_now);
return;
}
if (start_point > target)
{
return;
}
for (int i = start_point + 1; i <= total_area; i++)
{
if (degree[start_point][i] == 0)
{
continue;
}
int past = degree_now;
degree_now = max(degree_now, degree[start_point][i]);
dfs(i);
degree_now = past;
}
}
int main()
{
cin >> total_area >> total_road;
cin >> start >> target;
if (start > target)
{
int body = start;
start = target;
target = body;
}
for (int i = 0; i < total_road; i++)
{
int bind_1, bind_2;
cin >> bind_1 >> bind_2;
int body = 0;
cin >> body;
if (degree[bind_1][bind_2] != 0 && body < degree[bind_1][bind_2])
{
degree[bind_1][bind_2] = body;
degree[bind_2][bind_1] = body;
}
else if (degree[bind_1][bind_2] == 0)
{
degree[bind_1][bind_2] = body;
degree[bind_2][bind_1] = body;
}
}
// for (int i = 1; i <= total_area; i++)
// {
// for (int j = 1; j <= total_area; j++)
// {
// cout << degree[i][j];
// }
// cout << endl;
// }
dfs(start);
cout << min_degree;
return 0;
}
回复
共 7 条回复,欢迎继续交流。
正在加载回复...