社区讨论

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 条回复,欢迎继续交流。

正在加载回复...