[USACO09NOV] Job Hunt S – 最短路

有 \(C\leq 220\) 座城市，当前处在城市 \(S\)，在同一座城市最多赚 \(D \leq 1000\) 元后就要搬迁，有 \(P \leq 150\) 条免费单向道路，有 \(F\leq 350\) 条收费单向航线。可以在任意城市退休。问最多能赚多少钱，或者能永远赚下去。

Solution

难度：L2

将每个城市拆点成入点出点，入点向出点连边，费用为能赚的钱的相反数，出点向其它点的入点连边，费用为道路价格。如果有负环则能永远赚下去，否则输出 d[] 的最小值即可

#include <bits/stdc++.h>
using namespace std;
#define reset3f(x) memset(x,0x3f,sizeof x)
#define reset(x) memset(x,0,sizeof x)
const int N = 10005;
vector<pair<int,int> > g[N];

void make(int t1,int t2,int t3) {
    g[t1].push_back(make_pair(t2,t3));
}

namespace neg {
int n,m,ins[1000005],vis[1000005],dis[1000005],fg=0,t1,t2,t3,T;
void dfs(int p){
    ins[p]=1; vis[p]=1;
    for(int i=0;i<g[p].size()&&!fg;i++)
        if(dis[g[p][i].first]>dis[p]+g[p][i].second){
            dis[g[p][i].first]=dis[p]+g[p][i].second;
            if(ins[g[p][i].first]==0)
                dfs(g[p][i].first);
            else {fg=1; return;}}
    ins[p]=0;
}
}

namespace sp {
const int N=1e+6+5;
int n,v0=1,d[N],v[N];
void solve() {
    queue <int> qu;
    reset(v); reset3f(d);
    d[v0]=0; v[v0]=1; qu.push(v0);
    while(qu.size()) {
        int p=qu.front();
        qu.pop();
        v[p]=0;
        for(int i=0;i<g[p].size();i++) {
            int q=g[p][i].first,w=g[p][i].second;
            if(d[q]>d[p]+w) {
                d[q]=d[p]+w;
                if(!v[q]) qu.push(q), v[q]=1;
            }
        }
    }
}
}

int d,p,c,f,s,t1,t2,t3;

signed main() {
    ios::sync_with_stdio(false);
    cin>>d>>p>>c>>f>>s;
    for(int i=1;i<=p;i++) {
        cin>>t1>>t2;
        make(t1+c,t2,0);
    }
    for(int i=1;i<=f;i++) {
        cin>>t1>>t2>>t3;
        make(t1+c,t2,t3);
    }
    for(int i=1;i<=c;i++) {
        make(i,i+c,-d);
    }
    neg::dfs(s);
    if(neg::fg) {
        cout<<-1;
    }
    else {
        sp::v0=s;
        sp::solve();
        cout<<-*min_element(sp::d+1,sp::d+2*c+1);
    }
}