题目传送门：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; else right = 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"); else printf("%d\n",ans); } return 0; }
