题意：Dima和Inna越来越喜欢对方，但是Dima的室友缺很没有热情出去玩，然后Dima就把他室友Seryozha骗进了陷阱里。现在Seryozha想要从陷阱里出来，每条路上有一个l,r， Seryozha在走路前可以选择一个X，然后每次通过一条路的时候都需要满足条件 l <= x <= r, 每次选定了一个X之后，这个X是一个定值，不会乱变，现求这样的X的数目一共有多少，如果为0就输出“Nick work Dima!”，不然就输出数目。
题解：在每个点开一个set，存一下每次访问到这个点的时候的左区间，右区间，如果访问过了，那就不需要再走了，因为结果肯定不会比完全覆盖的更优，当然如果现在的长度已经小于等于ans的长度了，那么也不再需要再走了，就算接下来的路都不限制区间，那么也不可能比答案更优。
1 #include<iostream> 2 #include<vector> 3 #include<set> 4 #include<queue> 5 #include<cstring> 6 using namespace std; 7 const int INF = 0x3f3f3f3f; 8 const int N = 1e3+5; 9 typedef pair<int, int> pll; 10 struct Node 11 { 12 int b, l, r; 13 }tmp; 14 vector<Node> edge[N]; 15 set<pll> len[N]; 16 int n, m, ans = 0; 17 void Add_edge(int a, int b, int l, int r) 18 { 19 tmp.b = b; 20 tmp.l = l, tmp.r = r; 21 edge[a].push_back(tmp); 22 } 23 void solve() 24 { 25 queue<Node> q; 26 tmp.b = 1, tmp.l = 0, tmp.r = INF; 27 q.push(tmp); 28 set<pll>::iterator it; 29 while(!q.empty()) 30 { 31 tmp = q.front(); 32 q.pop(); 33 int id = tmp.b; 34 int l = tmp.l, r = tmp.r; 35 if(id == n) 36 { 37 ans = max(ans, r-l+1); 38 continue; 39 } 40 if(r-l+1 <= ans) continue; 41 for(int i = 0; i < edge[id].size(); i++) 42 { 43 int ll = max(l, edge[id][i].l); 44 int rr = min(r, edge[id][i].r); 45 int t = edge[id][i].b; 46 if(ll > rr) continue; 47 bool flag = 0; 48 for(it = len[t].begin(); it != len[t].end(); it++) 49 { 50 if((*it).first <= ll && (*it).second >= rr) 51 { 52 flag = 1; 53 break; 54 } 55 } 56 if(flag) continue; 57 len[t].insert(pll(ll,rr)); 58 tmp.b = t; 59 tmp.l = ll; 60 tmp.r = rr; 61 q.push(tmp); 62 } 63 } 64 } 65 int main() 66 { 67 ios::sync_with_stdio(false); 68 cin.tie(0); 69 cout.tie(0); 70 int a, b, l, r; 71 cin >> n >> m; 72 for(int i = 1; i <= m; i++) 73 { 74 cin >> a >> b >> l >> r; 75 Add_edge(a,b,l,r); 76 Add_edge(b,a,l,r); 77 } 78 solve(); 79 if(ans == 0) cout << "Nice work, Dima! "; 80 else cout << ans << endl; 81 return 0; 82 }