题目传送门：http://codeforces.com/problemset/problem/366/D
题意：有n个点m条无向边。初始你需要选择一个整数x，走第i条边的限制为Li <= x <= Ri，假设1-n的一条路径上可以选择的整数x有ans个，问你最大的ans。
分析：因为答案肯定是这些边中最优左端点到某个右端点的，所以就成了在已知左端点的情况下，维护最大的右端点。二分右端点，dfs验证是否可行即可。
#include<bits/stdc++.h>
#define PI acos(-1.0)
#define eps 1e-8
#define ll long long
#define MEM(a, b) memset(a, b, sizeof(a))
#define pb push_back
#define mp make_pair
#define MII map<int,int>::iterator
#define MLL map<LL,LL>::iterator
#define pii pair<int,int>
#define si set<int>::iterator
#define sl set<LL>::iterator
#define bug printf("bug-------bug-------bug\n")
using namespace std;
const int maxn = 1005;
int Time, head[maxn], vis[maxn], eid, ans, n, m;
bool success;
set<int> st;
struct Edge
{int to, x, y, nxt;
}edge[6010];
void addedge(int u, int v, int l, int r)
{edge[eid].to = v;edge[eid].x = l;edge[eid].y = r;edge[eid].nxt = head[u];head[u] = eid++;
}
void dfs(int u, int l, int r)
{if(success)return;if(u == n){success = true;return;}for(int i = head[u]; i != -1; i = edge[i].nxt){int v = edge[i].to;if(vis[v] == Time || edge[i].x > l || edge[i].y < r)continue;vis[v] = Time;dfs(v, l, r);}
}
void solve()
{ans = 0;for(si i = st.begin(); i != st.end(); i++){int now = *i;int left = now, right = 1e6+5, mid;while(left < right){Time++;success = false;vis[1] = Time;mid = (left + right) / 2;dfs(1, now, mid);if(success)left = mid + 1;elseright = mid;}ans = max(ans, left - now);}
}
int main()
{Time = 1;memset(vis, 0, sizeof(vis));while(cin >> n >> m){eid = 0;memset(head, -1, sizeof(head));st.clear();while(m--){int u, v, l, r;cin >> u >> v >> l >> r;addedge(u, v, l, r);addedge(v, u, l, r);st.insert(l);st.insert(r);}solve();if(ans == 0)printf("Nice work, Dima!\n");elseprintf("%d\n",ans);}return 0;
}