G - Travel HDU - 4284——floyd+dfs

清疚 2022-06-11 01:25 113阅读 0赞

Think:  
1知识点：floyd(需要判断重边)+dfs  
2题意分析：PP要到一些城市去旅游，但是他的钱不一定足够，因此会在必须去的城市购买一次签证进而挣钱，近经过城市不需要购买签证，题目给定n个城市,m条边，询问PP从1号城市出发是否可以去所有必须去的城市，是输出YES,否输出NO  
3思路：floyd预处理城市之间能够互达的最少花费，dfs暴力搜索每一条可能的路径  
4可能优化思路：搜索题解发现有的dalao用状压dp，准备开始学习数位dp, 状压dp

[vjudge题目链接][vjudge]

[建议参考博客][Link 1]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    
    struct Node{
        int num;
        int ci;
        int di;
    }bla[114];
    
    int e[114][114], vis[114], mon, cd;
    
    void Init(int n);
    void Floyd(int n);
    bool dfs(int x, int step);
    
    int main(){
        int T, n, m, u, v, w, i;
        scanf("%d", &T);
        while(T--){
            scanf("%d %d %d", &n, &m, &mon);
            Init(n);
            for(i = 1; i <= m; i++){
                scanf("%d %d %d", &u, &v, &w);
                e[u][v] = e[v][u] = min(e[u][v], w);
            }
            Floyd(n);
            scanf("%d", &cd);
            for(i = 1; i <= cd; i++){
                scanf("%d %d %d", &bla[i].num, &bla[i].ci, &bla[i].di);
            }
            memset(vis, 0, sizeof(vis));
            if(dfs(1, 0))
                printf("YES\n");
            else
                printf("NO\n");
        }
        return 0;
    }
    void Init(int n){
        for(int i = 1; i <= n; i++){
            e[i][i] = 0;
            for(int j = i+1; j <= n; j++){
                e[i][j] = e[j][i] = inf;
            }
        }
    }
    void Floyd(int n){
        int i, j, k;
        for(k = 1; k <= n; k++){
            for(i = 1; i <= n; i++){
                for(j = 1; j <= n; j++){
                    if(e[i][k] + e[k][j] < e[i][j])
                        e[i][j] = e[i][k] + e[k][j];
                }
            }
        }
    }
    bool dfs(int x, int step){
        if(step == cd && mon >= e[x][1])
            return true;
        for(int i = 1; i <= cd; i++){
            if(!vis[bla[i].num] && e[x][bla[i].num] != inf && mon - e[x][bla[i].num] >= bla[i].di){
                vis[bla[i].num] = 1;
                mon = mon - e[x][bla[i].num] - bla[i].di + bla[i].ci;
                if(dfs(bla[i].num, step+1))
                    return true;
                vis[bla[i].num] = 0;
                mon = mon + e[x][bla[i].num] + bla[i].di - bla[i].ci;
            }
        }
        return false;
    }

[vjudge]: https://vjudge.net/contest/173668#problem/G
[Link 1]: http://blog.csdn.net/u012841845/article/details/18900203