[CodeVS 月赛 #7 day1] FFF 团卧底的后宫

发表于   |  

Solution

裸的差分约束系统
不过因为太久没打。。居然打成了最长路。。。
a-b<=y应该是跑最短路的啊
我稍微推一下免得又搞错了
dis[a]-dis[b]\<=w[b,a]
–> w[b,a]+dis[b] >= dis[a]
–> if dis[b]+w[b,a] < dis[a] then dis[a] = dis[b]+w[b,a] 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
#define LL long long
#define maxm 100000
#define maxn 1000+100
using namespace std;
int n,m1,m2,e;
struct data{
    int v,w,nex;
}d[maxm];
int dis[maxn],fir[maxn];
void addedge(int u,int v,int w){
    d[++e].v=v;
    d[e].w=w;
    d[e].nex=fir[u];
    fir[u]=e;
}
queue <int> q;
bool inq[maxn];
int num[maxn];
int raw;
void spfa(){
    memset(dis,127,sizeof dis);
    raw=dis[n];
    dis[1]=0;
    q.push(1);
    num[1]=1;
    while (!q.empty()){
        int u=q.front();
        q.pop();
        inq[u]=false;
        for (int i=fir[u];i; i=d[i].nex){
            //cout<<i<<endl;
            int v=d[i].v,w=d[i].w;
            if (dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                if (!inq[v]){
                    if (num[v]>=n) {
                        printf(""-1"");
                        return;
                    }
                    inq[v]=true;
                    num[v]++;
                    q.push(v);
                }
            }
        }
    }
    if (dis[n]==raw) printf(""-2"");
    else printf(""%d"",dis[n]);
}
int main(){

    scanf(""%d%d%d"",&n,&m1,&m2);
    for (int i=1;i<=m1;i++){
        int a,b,w;
        scanf(""%d%d%d"",&a,&b,&w);
        addedge(a,b,w);
    }
     for (int i=1;i<=m2;i++){
        int a,b,w;
        scanf(""%d%d%d"",&a,&b,&w);
        addedge(b,a,-w);
    }
    spfa();
    return 0;
}