S - Layout ——最短路_spfa()算法+前向星+负环+差分约束

快来打我* 2022-06-12 10:53 181阅读 0赞

Think:  
1知识点：最短路\_spfa()算法+前向星+负环+差分约束  
2题意分析：ml关系的奶牛距离小于等于w,md关系的奶牛距离大于等于w,询问满足条件的情况下1与n之间的最大距离，模型抽象发现不等式组

[vjudge题目链接][vjudge]

[可参考博客][Link 1]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const int N = 1e3 + 4;
    const int M = 2e4 + 4;
    
    struct Edge{
        int v;
        int w;
        int next;
    }edge[M];
    
    bool flag;
    int n, ml, md, cnt, head[N], dis[N], vis[N], num[N];
    
    void add_edge(int u, int v, int w);
    void spfa(int x);
    
    int main(){
        int i, u, v, w;
        while(~scanf("%d %d %d", &n, &ml, &md)){
            flag = true, cnt = 0;
            memset(head, -1, sizeof(head));
            for(i = 1; i <= ml; i++){
                scanf("%d %d %d", &u, &v, &w);
                if(u > v)
                    swap(u, v);
                add_edge(u, v, w);/*差分约束*/
            }
            for(i = 1; i <= md; i++){
                scanf("%d %d %d", &u, &v, &w);
                if(u < v)
                    swap(u, v);
                add_edge(u, v, -w);/*差分约束*/
            }
            spfa(1);
            if(!flag)
                printf("-1\n");
            else
                printf("%d\n", dis[n] == inf? -2: dis[n]);
        }
        return 0;
    }
    void add_edge(int u, int v, int w){
        edge[cnt].v = v;
        edge[cnt].w = w;
        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 u = q.front();
            q.pop();
            vis[u] = 0;
            for(int i = head[u]; ~i; i = edge[i].next){
                int v = edge[i].v;
                int w = edge[i].w;
                if(dis[u] + w < dis[v]){
                    dis[v] = dis[u] + w;
                    if(!vis[v]){
                        vis[v] = 1;
                        q.push(v);
                        num[v]++;
                    }
                    if(num[v] > n){
                        flag = false;
                        return;
                    }
                }
            }
        }
    }

[vjudge]: https://vjudge.net/contest/163006#problem/S
[Link 1]: http://www.cnblogs.com/kuangbin/archive/2012/08/17/2644643.html