首页 > 代码库 > 差分约束Poj 3169 Layout
差分约束Poj 3169 Layout
?
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; } |
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。