Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 13706 | Accepted: 6581 |
Description
Some cows like each other and want to be within a certain distance of each other in line. Some really dislike each other and want to be separated by at least a certain distance. A list of ML (1 <= ML <= 10,000) constraints describes which cows like each other and the maximum distance by which they may be separated; a subsequent list of MD constraints (1 <= MD <= 10,000) tells which cows dislike each other and the minimum distance by which they must be separated.
Your job is to compute, if possible, the maximum possible distance between cow 1 and cow N that satisfies the distance constraints.
Input
Lines 2..ML+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at most D (1 <= D <= 1,000,000) apart.
Lines ML+2..ML+MD+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at least D (1 <= D <= 1,000,000) apart.
Output
Sample Input
4 2 1
1 3 10
2 4 20
2 3 3
Sample Output
27
Hint
There are 4 cows. Cows #1 and #3 must be no more than 10 units apart, cows #2 and #4 must be no more than 20 units apart, and cows #2 and #3 dislike each other and must be no fewer than 3 units apart.
The best layout, in terms of coordinates on a number line, is to put cow #1 at 0, cow #2 at 7, cow #3 at 10, and cow #4 at 27.
Source
#include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define MAXN 1001000 using namespace std; queue<int>que; int n,ml,md,tot,flag; int vis[MAXN],dis[MAXN],cnt[MAXN]; int to[MAXN],net[MAXN],cap[MAXN],head[MAXN]; void add(int u,int v,int w){ to[++tot]=v;cap[tot]=w;net[tot]=head[u];head[u]=tot; } void spfa(){ memset(vis,0,sizeof(vis)); memset(dis,0x7f,sizeof(dis)); dis[1]=0;vis[1]=1; cnt[1]++;que.push(1); while(!que.empty()){ int now=que.front(); que.pop();vis[now]=0; for(int i=head[now];i;i=net[i]) if(dis[to[i]]>dis[now]+cap[i]){ dis[to[i]]=dis[now]+cap[i]; if(!vis[to[i]]){ if(++cnt[to[i]]>n){ printf("-1");exit(0); } vis[to[i]]=1; que.push(to[i]); } } } if(dis[n]==2139062143) printf("-2"); else printf("%d",dis[n]);exit(0); } int main(){ scanf("%d%d%d",&n,&ml,&md); for(int i=1;i<=ml;i++){ int a,b,d; scanf("%d%d%d",&a,&b,&d); add(a,b,d); } for(int i=1;i<=md;i++){ int a,b,d; scanf("%d%d%d",&a,&b,&d); add(b,a,-d); } for(int i=1;i<=n;i++) add(i,i-1,0); spfa(); }