首页 > 代码库 > 差分约束Poj 3169 Layout

差分约束Poj 3169 Layout

2024-07-07 04:36:13   231人阅读

?
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
70
71
72
73
74
75
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <string>
#include <iostream>
using namespace std;
int n;
const int INF=0xfffffff;
struct edge
{
    int val;int to;int next;
}e[111111];
 
int len;int head[11111];
 
void add(int from,int to,int val)
{
    e[len].to=to;e[len].val=val;e[len].next=head[from];head[from]=len++;
}
int dis[11111];
int spfa(int x)
{
    int vis[11111];
    for(int i=1;i<=n;i++) vis[i]=0;
    for(int i=1;i<=n;i++) dis[i]=INF;
    vis[x]=1; dis[x]=0;
    queue<int> q;
    q.push(x);  int cnt[11111]={0}; cnt[x]=1;
    while(!q.empty()){
        int cur=q.front(); q.pop();vis[cur]=0;
        for(int i=head[cur];i!=-1;i=e[i].next){
            int cc=e[i].to;
            if(dis[cc]>dis[cur]+e[i].val){
                dis[cc]=dis[cur]+e[i].val;
                if(!vis[cc]){
                    cnt[cc]++;if(cnt[cc]>n) return 0;
                    q.push(cc); vis[cc]=1;
                }
            }
        }
    }
    return 1;
}
 
int main()
{
    int m,l;
    while(scanf("%d%d%d",&n,&m,&l)!=EOF){
        len=0;memset(head,-1,sizeof(head));
        for(int i= 0;i<m;i++){
            int a,b,c;scanf("%d%d%d",&a,&b,&c);
            if(a>b) {int t=a;a=b;b=t;}
            add(a,b,c);
        }
        for(int i=0;i<l;i++){
            int a,b,c;scanf("%d%d%d",&a,&b,&c);
            if(a<b){int t=a;a=b;b=t;};
            add(a,b,-c);
        }
        if(!spfa(1)) printf("-1\n");
        else{
            if(dis[n]==INF)
                printf("-2\n");
            else
                printf("%d\n",dis[n]);
        }
    }
    return 0;
}

　　

 


联系
我们