历年上机题 ---I Wanna Go Home

ゝ一纸荒年。 2023-07-22 09:28 3阅读 0赞

[https://www.nowcoder.com/practice/0160bab3ce5d4ae0bb99dc605601e971?tpId=61&tqId=29500&tPage=1&ru=/kaoyan/retest/1002&qru=/ta/pku-kaoyan/question-ranking][https_www.nowcoder.com_practice_0160bab3ce5d4ae0bb99dc605601e971_tpId_61_tqId_29500_tPage_1_ru_kaoyan_retest_1002_qru_ta_pku-kaoyan_question-ranking]

思路：这个我一开始没想通。后面再讨论区里面发现了一个非常好的思路。

因为要求从点1到点2，且最多只能经过一条边的两端的点处于不同的阵营。如何在求最短路的同时，满足这个限制要求呢？其实我们可以这样，如何某条边连接了两个不同的阵营，那么就限制这条边只能从一个方向走（即规定，只能从阵营1到阵营2）。其实当我们做了这样的规定以后，我们就可以直接用Floyd来做了，因为我们已经满足了题意。

如果不能理解的话，建议直接画一个图。

#include <bits/stdc++.h>
    using namespace std;
    #define INF 99999999
    const int maxn = 610;
    const int maxm = 10010;
    int n;
    int dp[maxn][maxn];
    int leader[maxn];
     
    void floyd(){
       for(int k = 1; k <= n; ++k){
            for(int i = 1; i <= n; ++i){
                for(int j = 1; j <= n; ++j){
                     dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
                    }
                }
            }
    }
     
    int main(){
        int m, a, b, c;
        while(cin >> n >> m && n != 0){
            for(int i = 1; i <= n; ++i){
                for(int j = 1; j <= n; ++j){
                    if(i == j) dp[i][j] = 0;
                    dp[i][j] = INF;
                }
            }
            for(int i = 0; i < m; ++i){
                cin >> a >> b >> c;
                if(dp[a][b] > c){
                    dp[a][b] = dp[b][a] = c;
                    //一开始边应该先保证是双向的
                }
            }
            for(int i = 1; i <= n; ++i){
                cin >> leader[i];
            }
            for(int i = 1; i <= n; ++i){
                for(int j = 1; j <= n; ++j){
                    //只要把不在一个阵营的边设置成有向边即可：leader1->deader2通，leader2->leader1不通
                    if(leader[i] == 2 && leader[j] == 1){
                        dp[i][j] = INF;
                    }
                }
            }
            floyd();
            if(dp[1][2] == INF) cout << "-1" << endl;
            else cout << dp[1][2] << endl;
        }
     
        return 0;
    }

[https_www.nowcoder.com_practice_0160bab3ce5d4ae0bb99dc605601e971_tpId_61_tqId_29500_tPage_1_ru_kaoyan_retest_1002_qru_ta_pku-kaoyan_question-ranking]: https://www.nowcoder.com/practice/0160bab3ce5d4ae0bb99dc605601e971?tpId=61&tqId=29500&tPage=1&ru=/kaoyan/retest/1002&qru=/ta/pku-kaoyan/question-ranking