C - Heavy Transportation——spfa()算法

今天药忘吃喽~ 2022-06-12 05:13 153阅读 0赞

Think:  
1知识点：spfa()算法+最短路径变形  
2题意：求n = 1的点到 n = n 的所有可达路径中（当前路径权值最小的）最大值  
3反思：注意不要忘记e数组初始化

以下为Wrong Answer代码——题意理解错误

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

以下为Wrong Answer代码——e数组未初始化

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

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const int N = 1014;
    
    int n, m, e[N][N], vis[N], dis[N];
    
    void spfa(int x);
    
    int main(){
        int k = 1, T, i, u, v, w;
        scanf("%d", &T);
        while(T--){
            scanf("%d %d", &n, &m);
            memset(e, 0, sizeof(e));/*注意不要忘记初始化*/
            for(i = 0; i < m; i++){
                scanf("%d %d %d", &u, &v, &w);
                e[u][v] = e[v][u] = w;
            }
            spfa(1);
            printf("Scenario #%d:\n", k++);
            printf("%d\n", dis[n]);
            printf("\n");
        }
        return 0;
    }
    void spfa(int x){
        queue <int> q;
        while(!q.empty()){
            q.pop();
        }
        memset(vis, 0, sizeof(vis));
        memset(dis, 0, sizeof(dis));
        vis[x] = 1, dis[x] = inf;
        q.push(x);
        while(!q.empty()){
            int u = q.front();
            q.pop();
            vis[u] = 0;
            for(int i = 1; i <= n; i++){
                if(min(dis[u], e[u][i]) > dis[i]){
                    dis[i] = min(dis[u], e[u][i]);
                    if(!vis[i]){
                        vis[i] = 1;
                        q.push(i);
                    }
                }
            }
        }
    }