http://codeforces.com/contest/366/problem/D
遍历下界，然后用二分求上界，然后用dfs去判断是否可以。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 10000 5 using namespace std; 6 7 int n,m; 8 int head[maxn]; 9 bool vis[maxn]; 10 int e; 11 int pl[maxn],pr[maxn]; 12 int ans; 13 struct node 14 { 15 int u,v; 16 int l,r; 17 int next; 18 }p[maxn*4]; 19 20 void inti() 21 { 22 memset(vis,false,sizeof(vis)); 23 memset(head,-1,sizeof(head)); 24 e=0; 25 } 26 27 void add(int u,int v,int l,int r) 28 { 29 p[e].u=u; 30 p[e].v=v; 31 p[e].l=l; 32 p[e].r=r; 33 p[e].next=head[u]; 34 head[u]=e++; 35 } 36 37 bool dfs(int u,int l,int r) 38 { 39 if(l>r) return false; 40 vis[u]=true; 41 if(u==n) return true; 42 for(int i=head[u]; i!=-1; i=p[i].next) 43 { 44 int v=p[i].v,ll=p[i].l,rr=p[i].r; 45 if(!vis[v]) 46 { 47 if(ll<=l&&rr>=r) 48 { 49 if(dfs(v,l,r)) return true; 50 } 51 } 52 } 53 return false; 54 } 55 56 57 int main() 58 { 59 while(scanf("%d%d",&n,&m)!=EOF) 60 { 61 inti(); 62 int u,v,l,r; 63 int cnt=0; 64 for(int i=1; i<=m; i++) 65 { 66 scanf("%d%d%d%d",&u,&v,&l,&r); 67 add(u,v,l,r); 68 add(v,u,l,r); 69 pl[cnt]=l; 70 pr[cnt++]=r; 71 } 72 ans=-1; 73 sort(pl,pl+cnt); 74 sort(pr,pr+cnt); 75 for(int i=0; i<cnt; i++) 76 { 77 int l1=0; 78 int r1=cnt; 79 int mid=(l1+r1)>>1; 80 while(l1<r1) 81 { 82 memset(vis,false,sizeof(vis)); 83 if(dfs(1,pl[i],pr[mid])) l1=mid+1; 84 else r1=mid; mid=(l1+r1)>>1; 85 } 86 if(pl[i]<=pr[mid-1]) 87 { 88 ans=max(ans,pr[mid-1]-pl[i]+1); 89 } 90 } 91 if(ans==-1) printf("Nice work, Dima! "); 92 else printf("%d ",ans); 93 } 94 return 0; 95 }