C--最短路（Bellman-Ford或者SPFA）

今天药忘吃喽~ 2022-07-12 08:54 83阅读 0赞

think:  
1题目由题意可知输入数据很大，而且顶点数达到了500000，如果用Dijkstra算法和Floyd算法定义的二维数组都无法达到500000\*500000,因此可以考虑使用Bellma-Ford算法，不过得使用标记变量check用来标记数组dis在本轮松弛中是否发生了变化  
2注意有权无向图  
3题意提示权值大于等于0，如果权值存在小于零，适合用Belloc-Ford算法或Bellman-Ford算法的队列优化了  
4反思：自己在t的变化上忽视了在每次循环中应使用两次t++，导致了有效数据被覆盖，数组一开始开小了，但自己感觉计算就应该是1<=n<=50000,1<=m<=200000，以后需要注意留心仔细一点  
5尝试推测题意考察点，把握重点，注意细节  
6刚才又学习了SPFA算法，用SPFA算法实现了一下，可能因为后台数据比较类型相似，两种算法实现的时间差不多，可能自己因为刚学习，一些SPFA算法的优化还不会，自己想同样加标记变量，结果可能加标记变量后一些位置重新松弛的时候变化不对，因此结果wrong answer，自己应该继续深入学习，争取学会SPFA算法很好的优化  
7SPFA算法（Bellman-Ford算法的队列优化）  
8Floyd算法的时间复杂度为O(N^3),Dijkstra算法的时间复杂度为O((M + N)logN),堆优化的Dijkstra算法时间复杂度可以达到O(MlogN),而Bellman-Ford算法的时间复杂度为O(NM),队列优化的Bellman-Ford算法时间复杂度最坏也是O(NM)  
9Floyd算法和Dijkstra算法适合于稠密图，和顶点关系密切,而Bellman-Ford算法与队列优化的Bellman-Ford算法适合于稀疏图，和边关系密切

[sdut原题链接][sdut]

C–最短路  
Time Limit: 7000MS Memory Limit: 65536KB

Problem Description  
给出一个带权无向图，包含n个点，m条边。求出s，e的最短路。保证最短路存在。

Input  
多组输入。  
对于每组数据。  
第一行输入n，m(1<= n && n<=5\*10^5,1 <= m && m <= 2\*10^6)。  
接下来m行，每行三个整数，u,v,w,表示u，v之间有一条权值为w(w >= 0)的边。  
最后输入s，e。

Output  
对于每组数据输出一个整数代表答案。

Example Input  
3 1  
1 2 3  
1 2

Example Output  
3

Hint

Author  
zmx

以下为accepted代码——Bellman-Ford

#include <stdio.h>
    #define INF 0x3f3f3f3f
    int dist[500004], u[4000004], v[4000004], w[4000004];
    int main()
    {
        int n, m, i, k, s, e, check, flag, t, x, y, z;
        while(scanf("%d %d", &n, &m) != EOF)
        {
            t = 1;
            for(i = 1; i <= m; i++)
            {
                scanf("%d %d %d", &x, &y, &z);
                u[t] = x, v[t] = y, w[t] = z;
                t++;
                u[t] = y, v[t] = x, w[t] = z;
                t++;///注意：使用之后一定要+1
            }
            scanf("%d %d", &s, &e);
    
            for(i = 1; i <= n; i++)
                dist[i] = INF;
            dist[s] = 0;
    
            m = 2*m;//有权无向图
    
            //Bellman-Ford算法核心语句
            for(k = 0; k < n-1; k++)
            {
                check = 0;
                for(i = 1; i <= m; i++)
                {
                    if(dist[v[i]] > dist[u[i]] + w[i])
                    {
                        dist[v[i]] = dist[u[i]] + w[i];
                        check = 1;
                    }
                }
                if(check == 0)
                    break;
            }
    
            //检测负权回路
            flag = 0;
            for(i = 1; i <= m; i++)
            {
                if(dist[v[i]] > dist[u[i]] + w[i])
                    flag = 1;
            }
            if(flag)
                printf("error because of -\n");
            else
                printf("%d\n", dist[e]);
        }
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 808ms
    Take Memory: 36672KB
    Submit time: 2017-02-19 16:33:18
    ****************************************************/

以下为accepted代码——SPFA算法

#include <stdio.h>
    #include <string.h>
    #define INF 0x3f3f3f3f
    int tp, op;
    int book[500004], link[500004];
    int dist[500004], u[4000004], v[4000004], w[4000004];
    int main()
    {
        int n, m, i, k, s, e, t, x, y, z;
        while(scanf("%d %d", &n, &m) != EOF)
        {
            tp = op = 0;
            memset(book, -1, sizeof(book));
            memset(link, 0, sizeof(link));
    
            t = 1;
            for(i = 1; i <= m; i++)
            {
                scanf("%d %d %d", &x, &y, &z);
                u[t] = x, v[t] = y, w[t] = z;
                t++;
                u[t] = y, v[t] = x, w[t] = z;
                t++;
            }
            scanf("%d %d", &s, &e);
    
            for(i = 1; i <= n; i++)
                dist[i] = INF;
            dist[s] = 0;
    
            m = 2*m;
            link[tp++] = v[s];
            book[s] = 1;
            while(op < tp)
            {
                op++;
                k = link[op];
                while(k <= m)
                {
                    if(dist[v[k]] > dist[u[k]] + w[k])
                    {
                        dist[v[k]] = dist[u[k]] + w[k];
                        if(book[k] == 0)
                        {
                            link[tp++] = v[k];
                            book[v[k]] = 1;
                        }
                    }
                    k++;
                }
            }
            printf("%d\n", dist[e]);
        }
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 860ms
    Take Memory: 52840KB
    Submit time: 2017-02-19 17:49:05
    ****************************************************/

[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2013/pid/2894