Ivan's Car URAL - 1930——前向星＋spfa算法

清疚 2022-06-14 09:59 178阅读 0赞

Think:  
1题意理解：从A结点到B结点，每次有两种状态，上或者下，上下交替时需要齿轮数量加一  
２思路：  
1>结点编号可达到10000，因此基本不能用邻接矩阵存储，所以思考前向星存储边和结点的关系  
2>一个结点到另一个结点，思考最短路径  
３反思：  
1>初始状态可以有两种操作，向上或者向下  
2>存储的是无向图，因此边的存储至少需要开临界边数的两倍

[建议参考博客：深度理解前向星][Link 1]

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <bits/stdc++.h>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    
    struct Edge{
        int next;
        int to;
        int w;
    }edge[204000];
    struct node {
        int flag;
        int id;
    }link[204000], t1, t2;
    
    int cnt, n, m, Begin, End, head[104000];
    int op, tp, ans, book[104000][2], dist[104000];
    
    void Init_head();
    void add_edge(int u, int v, int w);
    void spfa(int dir);
    
    
    
    int main(){
        int i, u, v;
        while(scanf("%d %d", &n, &m) != EOF){
            Init_head();
            cnt = 0;
            for(i = 1; i <= m; i++){
                scanf("%d %d", &u, &v);
                add_edge(u, v, 0);
                add_edge(v, u, 1);
            }
            scanf("%d %d", &Begin, &End);
            ans = inf;
            spfa(0);
            spfa(1);
            printf("%d\n", ans);
        }
        return 0;
    }
    void Init_head(){
        for(int i = 1; i <= n; i++)
            head[i] = -1;
    }
    void add_edge(int u, int v, int w){
        edge[cnt].w = w;
        edge[cnt].to = v;
        edge[cnt].next = head[u];
        head[u] = cnt++;
    }
    void spfa(int dir){
        op = tp = 0;
        memset(dist, inf, sizeof(dist));
        memset(book, 0, sizeof(book));
    
        link[tp].flag = dir;
        link[tp].id = Begin;
        tp++;
        book[Begin][dir] = 1;
        dist[Begin] = 0;
    
        int val;
        while(op < tp){
            t1 = link[op];
            int u = t1.id;
            book[t1.id][t1.flag] = 0;
            for(int i = head[u]; ~i; i = edge[i].next){
                int v = edge[i].to;
                if(t1.flag == edge[i].w)
                    val = 0;
                else
                    val = 1;
                if(dist[v] > dist[u] + val){
                    dist[v] = dist[u] + val;
                    t2.flag = edge[i].w;
                    t2.id = v;
                    if(!book[t2.id][t2.flag]){
                        book[t2.id][t2.flag] = 1;
                        link[tp++] = t2;
                    }
                }
            }
            op++;
        }
        ans = min(ans, dist[End]);
    }

[Link 1]: http://blog.csdn.net/acdreamers/article/details/16902023
[vjudge]: https://vjudge.net/problem/URAL-1930