AOE网上的关键路径——spfa+前向星

清疚 2022-06-12 03:53 202阅读 0赞

Think:  
1知识点：spfa+前向星  
2题目分析：字典序最小——逆序建图  
逆序建图原因：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JsZXNzaW5nWFJZ_size_16_color_FFFFFF_t_70]

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

[SDUT题目链接][SDUT]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    
    const int Inf = 0x3f3f3f3f;
    const int N = 10414;
    const int M = 50414;
    
    struct EdgeNode{
        int v, w, next;
    }edge[M];
    
    queue<int> que;
    
    int cnt, head[N], dis[N], vis[N], pre[N];
    int tp, link[N];
    int in[N], out[N];
    
    void Add(int u,int v, int w);
    void Spfa(int s, int e, int n);
    
    int main(){
        int n, m, u, v, w, s, e;
        while(~scanf("%d %d", &n, &m)){
            cnt = 0;
            memset(head, -1, sizeof(head));
            memset(in, 0, sizeof(in));
            memset(out, 0, sizeof(out));
            for(int i = 0; i < m; i++){
                scanf("%d %d %d", &u, &v, &w);
                // 逆序建图，得到字典序最小的
                Add(v, u, w);
                out[v]++, in[u]++;
            }
            for(int i = 1; i <= n; i++){
                if(in[i] == 0){
                    s = i;
                }
                if(out[i] == 0){
                    e = i;
                }
            }
            Spfa(s, e, n);
        }
        return 0;
    }
    void Add(int u, int v, int w){
        edge[cnt].v = v;
        edge[cnt].w = w;
        edge[cnt].next = head[u];
        head[u] = cnt++;
    }
    void Spfa(int s, int e, int n){
        int u, v;
        memset(dis, -Inf, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        memset(pre, Inf, sizeof(pre));
        while(!que.empty()){
            que.pop();
        }
        que.push(s);
        dis[s] = 0;
        vis[s] = 1;
        while(!que.empty()){
            u = que.front();
            que.pop();
            vis[u] = 0;
            for(int i = head[u]; ~i; i = edge[i].next){
                v = edge[i].v;
                if(dis[v] < dis[u]+edge[i].w || (dis[v] == dis[u]+edge[i].w && u < pre[v])){
                    dis[v] = dis[u] + edge[i].w;
                    pre[v] = u;
                    if(!vis[v]){
                        que.push(v);
                        vis[v] = 1;
                    }
                }
            }
        }
        printf("%d\n", dis[e]);
        tp = 0;
        for(int i = e; i != Inf; i = pre[i]){
            link[tp++] = i;
        }
        // 图是逆序建的
        for(int i = 0; i < tp-1; i++){
            printf("%d %d\n", link[i], link[i+1]);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JsZXNzaW5nWFJZ_size_16_color_FFFFFF_t_70]: /images/20220612/32232ced870c43f9ad3b7ec0c6a542e6.png
[Link 1]: http://blog.csdn.net/winddreams/article/details/41389831
[SDUT]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/2498.html