O - Extended Traffic——最短路_spfa()算法+前向星+判断负环

布满荆棘的人生 2022-06-12 10:40 180阅读 0赞

Think:  
1知识点：最短路\_spfa()算法+前向星+判断负环  
2反思：  
1>题意理解能力需要提高  
2>知识点理解不深入，需要多思考多应用  
3>前向星需要加深理解

[vjudge题目链接][vjudge]

[建议参考博客题意理解][Link 1]

以下为Compilation Error错误——编译环境语言选择错误

Main.c:1:18: fatal error: cstdio: No such file or directory
     #include 
                      ^
    compilation terminated.

以下为Wrong Answer代码——数组开小了且自己对前向星知识点理解浅显导致入队判断条件错误且入队元素错误且判断负环错误

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const int N = 1e2 + 4;
    const int M = 1e4 + 4;
    
    struct Edge{
        int v;
        int w;
        int next;
    }edge[M];
    
    int n, m, cnt, head[N], dis[N], vis[N], lev[N], num[N];
    
    void add_edge(int u, int v, int c);
    void spfa(int x);
    
    int main(){
        int T, k = 1, i, u, v, q, y;
        scanf("%d", &T);
        for(k = 1; k <= T; k++){
            cnt = 0;
            memset(head, -1, sizeof(head));
            scanf("%d", &n);
            for(i = 1; i <= n; i++){
                scanf("%d", &lev[i]);
            }
            scanf("%d", &m);
            for(i = 1; i <= m; i++){
                scanf("%d %d", &u, &v);
                add_edge(u, v, lev[v]-lev[u]);
            }
            spfa(1);
            printf("Case %d:\n", k);
            scanf("%d", &q);
            for(i = 1; i <= q; i++){
                scanf("%d", &y);
                if(dis[y] == inf || dis[y] < 3 || num[y] > n)
                    printf("?\n");
                else
                    printf("%d\n", dis[y]);
            }
        }
        return 0;
    }
    void add_edge(int u, int v, int c){
        edge[cnt].v = v;
        edge[cnt].w = c*c*c;
        edge[cnt].next = head[u];
        head[u] = cnt++;
    }
    void spfa(int x){
        queue <int> q;
        while(!q.empty()){
            q.pop();
        }
        memset(dis, inf, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        memset(num, 0, sizeof(num));
        dis[x] = 0, vis[x] = 1;
        q.push(x);
        num[x]++;
        while(!q.empty()){
            int t1 = q.front();
            q.pop();
            vis[t1] = 0;
            for(int i = head[t1]; ~i; i = edge[i].next){
                if(dis[t1] + edge[i].w < dis[edge[i].v]){
                    dis[edge[i].v] = dis[t1] + edge[i].w;
                    if((!vis[i]) && num[i] <= n){
                        q.push(edge[i].v);
                        num[i]++;
                    }
                }
            }
        }
    }

以下为Time limit Exceeded代码——自己对前向星知识点理解浅显导致入队判断条件错误且入队元素错误且判断负环错误

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const int N = 2e2 + 4;
    const int M = 1e4 + 4;
    
    struct Edge{
        int v;
        int w;
        int next;
    }edge[M];
    
    int n, m, cnt, head[N], dis[N], vis[N], lev[N], num[N];
    
    void add_edge(int u, int v, int c);
    void spfa(int x);
    
    int main(){
        int T, k = 1, i, u, v, q, y;
        scanf("%d", &T);
        for(k = 1; k <= T; k++){
            cnt = 0;
            memset(head, -1, sizeof(head));
            scanf("%d", &n);
            for(i = 1; i <= n; i++){
                scanf("%d", &lev[i]);
            }
            scanf("%d", &m);
            for(i = 1; i <= m; i++){
                scanf("%d %d", &u, &v);
                add_edge(u, v, lev[v]-lev[u]);
            }
            spfa(1);
            printf("Case %d:\n", k);
            scanf("%d", &q);
            for(i = 1; i <= q; i++){
                scanf("%d", &y);
                if(dis[y] == inf || dis[y] < 3 || num[y] > n)
                    printf("?\n");
                else
                    printf("%d\n", dis[y]);
            }
        }
        return 0;
    }
    void add_edge(int u, int v, int c){
        edge[cnt].v = v;
        edge[cnt].w = c*c*c;
        edge[cnt].next = head[u];
        head[u] = cnt++;
    }
    void spfa(int x){
        queue <int> q;
        while(!q.empty()){
            q.pop();
        }
        memset(dis, inf, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        memset(num, 0, sizeof(num));
        dis[x] = 0, vis[x] = 1;
        q.push(x);
        num[x]++;
        while(!q.empty()){
            int t1 = q.front();
            q.pop();
            vis[t1] = 0;
            for(int i = head[t1]; ~i; i = edge[i].next){
                if(dis[t1] + edge[i].w < dis[edge[i].v]){
                    dis[edge[i].v] = dis[t1] + edge[i].w;
                    if((!vis[i]) && num[i] <= n){
                        q.push(edge[i].v);
                        num[i]++;
                    }
                }
            }
        }
    }

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const int N = 2e2 + 4;
    const int M = 1e4 + 4;
    
    struct Edge{
        int v;
        int w;
        int next;
    }edge[M];
    
    int n, m, cnt, head[N], dis[N], vis[N], lev[N], num[N];
    
    void add_edge(int u, int v, int c);
    void spfa(int x);
    
    int main(){
        int T, k = 1, i, u, v, q, y;
        scanf("%d", &T);
        for(k = 1; k <= T; k++){
            cnt = 0;
            memset(head, -1, sizeof(head));
            scanf("%d", &n);
            for(i = 1; i <= n; i++){
                scanf("%d", &lev[i]);
            }
            scanf("%d", &m);
            for(i = 1; i <= m; i++){
                scanf("%d %d", &u, &v);
                add_edge(u, v, lev[v]-lev[u]);
            }
            spfa(1);
    
            scanf("%d", &q);
            printf("Case %d:\n", k);
            for(i = 1; i <= q; i++){
                scanf("%d", &y);
                if(dis[y] == inf || dis[y] < 3 || num[y] > n)
                    printf("?\n");
                else
                    printf("%d\n", dis[y]);
            }
        }
        return 0;
    }
    void add_edge(int u, int v, int c){
        edge[cnt].v = v;
        edge[cnt].w = c*c*c;
        edge[cnt].next = head[u];
        head[u] = cnt++;
    }
    void spfa(int x){
        queue <int> q;
        while(!q.empty()){
            q.pop();
        }
        memset(dis, inf, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        memset(num, 0, sizeof(num));
    
        dis[x] = 0, vis[x] = 1;
        q.push(x);
        num[x]++;
    
        while(!q.empty()){
            int t1 = q.front();
            q.pop();
            vis[t1] = 0;
            for(int i = head[t1]; ~i; i = edge[i].next){
                if(dis[t1] + edge[i].w < dis[edge[i].v]){
                    dis[edge[i].v] = dis[t1] + edge[i].w;
                    if((!vis[edge[i].v]) && num[edge[i].v] <= n){
                        q.push(edge[i].v);
                        num[edge[i].v]++;
                    }
                }
            }
        }
    }

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