K - Candies——最短路_spfa()算法

浅浅的花香味﹌ 2022-06-12 09:29 193阅读 0赞

Think:  
1知识点：  
1>最短路\_spfa()算法+前向星  
2>差分约束系统：[差分约束系统——百度百科][Link 1]  
2思考：队列超时，栈通过——why?

[vjudge题目链接][vjudge]

[参考博客1][1]  
[参考博客2][2]

以下为Time Limit Exceeded代码——STL\_queue()

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const int N = 3e4 + 4;
    const int M = 15e4 + 4;
    
    struct Edge
    {
        int v;
        int w;
        int next;
    } e[M];
    
    int n, m, cnt, head[N], vis[N], dis[N];
    
    void add_edge(int u, int v, int w);
    void spfa(int x);
    
    int main()
    {
        int i, u, v, w;
        scanf("%d %d", &n, &m);
        cnt = 0;
        memset(head, -1, sizeof(head));
        for(i = 1; i <= m; i++)
        {
            scanf("%d %d %d", &u, &v, &w);
            add_edge(u, v, w);
        }
        spfa(1);
        printf("%d\n", dis[n]-dis[1]);
        return 0;
    }
    void add_edge(int u, int v, int w)
    {
        e[cnt].v = v;
        e[cnt].w = w;
        e[cnt].next = head[u];
        head[u] = cnt++;
    }
    void spfa(int x)
    {
        queue <int> q;
        memset(dis, inf, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        dis[1] = 0, vis[1] = 1;
        q.push(1);
        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);
                    }
                }
            }
        }
    }

以下为Accepted代码——STL\_stack()

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <stack>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const int N = 3e4 + 4;
    const int M = 15e4 + 4;
    
    struct Edge
    {
        int v;
        int w;
        int next;
    } e[M];
    
    int n, m, cnt, head[N], vis[N], dis[N];
    
    void add_edge(int u, int v, int w);
    void spfa(int x);
    
    int main()
    {
        int i, u, v, w;
        scanf("%d %d", &n, &m);
        cnt = 0;
        memset(head, -1, sizeof(head));
        for(i = 1; i <= m; i++)
        {
            scanf("%d %d %d", &u, &v, &w);
            add_edge(u, v, w);
        }
        spfa(1);
        printf("%d\n", dis[n]-dis[1]);
        return 0;
    }
    void add_edge(int u, int v, int w)
    {
        e[cnt].v = v;
        e[cnt].w = w;
        e[cnt].next = head[u];
        head[u] = cnt++;
    }
    void spfa(int x)
    {
        stack <int> s;
        memset(dis, inf, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        dis[1] = 0, vis[1] = 1;
        s.push(1);
        while(!s.empty())
        {
            int t1 = s.top();
            s.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;
                        s.push(e[i].v);
                    }
                }
            }
        }
    }

[Link 1]: https://baike.baidu.com/item/%E5%B7%AE%E5%88%86%E7%BA%A6%E6%9D%9F%E7%B3%BB%E7%BB%9F/5182920?fr=aladdin
[vjudge]: https://vjudge.net/contest/163006#problem/K
[1]: http://blog.csdn.net/yujuan_Mao/article/details/9407467
[2]: http://blog.sina.com.cn/s/blog_88705ca20100umcu.html