D - Silver Cow Party——最短路_spfa()算法-蒲公英云

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

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

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

建议参考题意分析

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;
                }
            }
        }
    }
}