[BZOJ 3126] Photo

[题目链接]

        https://www.lydsy.com/JudgeOnline/problem.php?id=3126

[算法]

        差分约束系统

        注意SPFA判负环的条件应为 ： 若所有点入队次数之和 > 点数 + 边数，说明有负环

[代码]

       

#include<bits/stdc++.h>
using namespace std;
#define MAXN 200010
const int inf = 2e9;

int n,m,tot;
int head[MAXN];

struct edge
{
    int to,w,nxt;
} e[MAXN << 2];

template <typename T> inline void read(T &x)
{
    int f = 1; x = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-')  f = -f;
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0';
    x *= f;
}
inline void addedge(int u,int v,int w)
{
    tot++;
    e[tot] = (edge){v,w,head[u]};
    head[u] = tot;
}
inline int spfa(int s)
{
    int l,r,cnt = 0;
    static int dist[MAXN];
    static bool inq[MAXN];
    priority_queue< int , vector< int > , greater< int > > q;
    while (!q.empty()) q.pop();
    for (register int i = 0; i <= n; i++)
    {
        dist[i] = inf;
        inq[i] = false;
    }
    q.push(s);
    dist[s] = 0;
    inq[s] = true;
    cnt = 1;
    while (!q.empty())
    {
        int u = q.top();
        q.pop();
        inq[u] = false;
        for (register int i = head[u]; i; i = e[i].nxt)
        {
            int v = e[i].to , w = e[i].w;
            if (dist[u] + w < dist[v])
            {
                dist[v] = dist[u] + w;
                if (!inq[v])
                {
                    cnt++;
                    if (cnt > 3 * m + 2 * n) return -1;
                    inq[v] = true;
                    q.push(v);
                }
            }
        }
    }
    return dist[n] == inf ? -1 : dist[n];
}

int main()
{
    
    read(n); read(m);
    for (register int i = 1; i <= m; i++) 
    {
        int a,b;
        read(a); read(b);
        if (a > b) swap(a,b);
        addedge(a - 1,b,1);
        addedge(b,a - 1,-1);
    }
    for (register int i = 1; i <= n; i++) 
    {
        addedge(i,i - 1,0);
        addedge(i - 1,i,1);
    }
    printf("%d
",spfa(0));
    
    return 0;
}