J - Invitation Cards——最短路_spfa()算法

超、凢脫俗 2022-06-12 09:16 178阅读 0赞

Think:  
1知识点：最短路\_spfa()算法+前向星  
2反思：  
1>函数中形参和实参的传递，数组传进的为地址，形参改变实参相应的改变，而传进的标记变量形参改变实参不改变  
2>遇到bug要精心debug

[vjudge题目链接][vjudge]

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

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const int N = 1e6 + 4;
    const int M = 1e6 + 4;
    
    struct Edge{
        int v;
        int w;
        int next;
    }e1[M*2], e2[M*2];
    
    int n, m, cnt1, cnt2, head1[N], head2[N], dis[N], vis[N];
    
    int add_edge(int u, int v, int w, struct Edge e[M*2], int head[N], int cnt);
    void spfa(int x, struct Edge e[M*2], int head[N]);
    
    int main(){
        int T, i, u, v, w;
        long long sum;
        scanf("%d", &T);
        while(T--){
            scanf("%d %d", &n, &m);
            sum = 0, cnt1 = cnt2 = 0;
            memset(head1, -1, sizeof(head1));
            memset(head2, -1, sizeof(head2));
            for(i = 1; i <= m; i++){
                scanf("%d %d %d", &u, &v, &w);
                cnt1 = add_edge(u, v, w, e1, head1, cnt1);
                cnt2 = add_edge(v, u, w, e2, head2, cnt2);
            }
            spfa(1, e1, head1);
            for(i = 1; i <= n; i++){
                sum += dis[i];
            }
            spfa(1, e2, head2);
            for(i = 1; i <= n; i++){
                sum += dis[i];
            }
            printf("%lld\n", sum);
        }
        return 0;
    }
    int add_edge(int u, int v, int w, struct Edge e[M*2], int head[N], int cnt){
        e[cnt].v = v;
        e[cnt].w = w;
        e[cnt].next = head[u];
        head[u] = cnt++;
        return cnt;
    }
    void spfa(int x, struct Edge e[M*2], int head[N]){
        queue <int> q;
        while(!q.empty()){
            q.pop();
        }
        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 = head[t1]; ~i; i = e[i].next){
                if(dis[t1] + e[i].w < dis[e[i].v]){
                    dis[e[i].v] = dis[t1] + e[i].w;
                    if(!vis[e[i].v]){
                        vis[e[i].v] = 1;
                        q.push(e[i].v);
                    }
                }
            }
        }
    }

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