D - Silver Cow Party——最短路_spfa()算法

怼烎@ 2022-06-12 05:54 174阅读 0赞

Think:  
1知识点：最短路\_spfa()算法  
2反思：图的初始化  
3思路：通过正向边spfa()求出回去的，反向边spfa()求出到达的

[建议参考题意分析][Link 1]

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const int N = 1e3 + 4;
    
    int n, e1[N][N], e2[N][N], dis[N], vis[N];
    
    void spfa(int x, int e[N][N]);
    
    int main(){
        int m, i, x, u, v, w, sum[N], mav;
        scanf("%d %d %d", &n, &m, &x);
        mav = 0;
        memset(sum, 0, sizeof(sum));
        memset(e1, inf, sizeof(e1));
        memset(e2, inf, sizeof(e2));
        for(i = 0; i < m; i++){
            scanf("%d %d %d", &u, &v, &w);
            e1[u][v] = w;
            e2[v][u] = w;
        }
        spfa(x, e1);
        for(i = 1; i <= n; i++)
            sum[i] += dis[i];
    
        spfa(x, e2);
        for(i = 1; i <= n; i++){
            mav = max(mav, sum[i]+dis[i]);
        }
        printf("%d\n", mav);
        return 0;
    }
    void spfa(int x, int e[N][N]){
        queue <int> q;
        memset(dis, inf, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        dis[x] = 0, vis[x] = 1;
        q.push(x);
        while(!q.empty()){
            int t1 = q.front();
            q.pop();
            vis[t1] = 0;
            for(int i = 1; i <= n; i++){
                if(dis[t1] + e[t1][i] < dis[i]){
                    dis[i] = dis[t1] + e[t1][i];
                    if(!vis[i]){
                        q.push(i);
                        vis[i] = 1;
                    }
                }
            }
        }
    }

[Link 1]: http://www.cnblogs.com/liuxin13/p/4653595.html
[vjudge]: https://vjudge.net/contest/163006#problem/D