codeforces 366D Dima and Trap Graph 题解(搜索+剪枝or二分+枚举)

D. Dima and Trap Graph time limit per test 3 seconds memory limit per test 256 megabytes input standard input output standard output

Dima and Inna love spending time together. The problem is, Seryozha isn't too enthusiastic to leave his room for some reason. But Dima and Inna love each other so much that they decided to get criminal...

Dima constructed a trap graph. He shouted: "Hey Seryozha, have a look at my cool graph!" to get his roommate interested and kicked him into the first node.

A trap graph is an undirected graph consisting of n nodes and m edges. For edge number k, Dima denoted a range of integers from lkto rk (lk ≤ rk). In order to get out of the trap graph, Seryozha initially (before starting his movements) should pick some integer (let's call it x), then Seryozha must go some way from the starting node with number 1 to the final node with number n. At that, Seryozha can go along edge k only if lk ≤ x ≤ rk.

Seryozha is a mathematician. He defined the loyalty of some path from the 1-st node to the n-th one as the number of integers x, such that if he initially chooses one of them, he passes the whole path. Help Seryozha find the path of maximum loyalty and return to his room as quickly as possible!

Input

The first line of the input contains two integers n and m (2 ≤ n ≤ 103, 0 ≤ m ≤ 3·103). Then follow m lines describing the edges. Each line contains four integers ak, bk, lk and rk (1 ≤ ak, bk ≤ n, 1 ≤ lk ≤ rk ≤ 106). The numbers mean that in the trap graph the k-th edge connects nodes ak and bk, this edge corresponds to the range of integers from lk to rk.

Note that the given graph can have loops and multiple edges.

Output

In a single line of the output print an integer — the maximum loyalty among all paths from the first node to the n-th one. If such paths do not exist or the maximum loyalty equals 0, print in a single line "Nice work, Dima!" without the quotes.

Examples input 4 4 1 2 1 10 2 4 3 5 1 3 1 5 2 4 2 7 output 6 input 5 6 1 2 1 10 2 5 11 20 1 4 2 5 1 3 10 11 3 4 12 10000 4 5 6 6 output Nice work, Dima! Note

Explanation of the first example.

Overall, we have 2 ways to get from node 1 to node 4: first you must go along the edge 1-2 with range [1-10], then along one of the two edges 2-4.

One of them contains range [3-5], that is, we can pass through with numbers 3, 4, 5. So the loyalty of such path is 3.

If we go along edge 2-4 with range [2-7], then we can pass through with numbers 2, 3, 4, 5, 6, 7. The loyalty is 6. That is the answer.

The edge 1-2 have no influence on the answer because its range includes both ranges of the following edges.

题目大意是：在一个图上有1-n个点，某些点之间连着一些边，每条边上能通过一些数字，有2个信息l和r，代表这条边能通过数字[l,r]，题目问你从点1走到点n能顺利通过的数字个数，如果没有数字能从1走到n，则输出“Nice work, Dima!”。

思路 ： 一个是搜索+剪枝，就是从1往下搜，搜到n，有两个小剪枝，一个是搜索过程中如果ans已经更新完了，当前搜索的边r-l小于ans那后面的根本不用搜了，因为它已经限制了后面的最大，另一个是如果当前点已经搜过一次了，再搜边的时候，如果 tl <= l && r <= tr，tr跟tl都是这个点之前搜边保留下的lr，也就是当前边的lr在之前边的范围里面，后面的完全不用搜了，因为它把区间给缩小了，如果并没有 tl <= l && r <= tr，范围在缩小也要搜一遍，因为之前是1 5 这条便 是 6 8看起来小了，但是后面万一的是 6 7那么15根本没用了。。但之前是15 这条 是 2 4 那么后面区间再怎样， 1 5永远比2 4 占的多。。。

说了这么多，上代码：

#include <iostream> #include <cstdio> #include <cstdio> #include <algorithm> #include <vector> #include <cstring> using namespace std; const int maxn = 1e5 + 5; const int INF = 1e7; struct node { int v, l, r; node(){}; node(int vv, int ll, int rr) : v(vv), l(ll), r(rr){} }; vector<node> v[maxn]; int n, m, ans, book[maxn], recl[maxn], recr[maxn], vis[maxn]; void dfs(int u, int l, int r) { if(u == n) { ans = max(ans, r-l+1); return; } for(int i = 0; i < v[u].size(); i++) { int to = v[u][i].v; if(book[to]) continue; int tl = max(v[u][i].l,l); int tr = min(v[u][i].r,r); if(tl > tr) continue; if(ans != -1 && tr - tl + 1 <= ans) continue; //这里是第一条优化，如果答案更新过了，区间变小的都不用搜了 if(vis[to] && recl[to] <= tl && recr[to] >= tr) continue; //这里是第二条优化， 记住recl[to]是to，搜索这条边的这个点 recl[to] = tl; recr[to] = tr; book[to] = 1; vis[to] = 1; dfs(to, tl, tr); book[to] = 0; } } int main() { scanf("%d%d", &n, &m); int a, b, l, r; memset(recl, 1, sizeof(recl)); memset(recr, -1, sizeof(recr)); for(int i = 0; i < m; i++) { scanf("%d%d%d%d", &a, &b, &l, &r); v[a].push_back(node(b, l, r)); v[b].push_back(node(a, l, r)); } ans = -1; book[1] = 1; recl[1] = INF; recr[1] = -INF; dfs(1, -INF, INF); if(ans == -1) { printf("Nice work, Dima!\n"); } else { printf("%d\n", ans); } return 0; }  另一种就是枚举l，二分r，这都没想到。。。这样dfs只需要判断能不能走到n就好了

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int maxn = 3e3 + 5; int L[maxn], R[maxn], n, m, book[maxn]; struct node { int v, l, r; node (){}; node(int vv, int ll, int rr): v(vv), l(ll), r(rr) {} }; vector<node> v[maxn]; int dfs(int u, int l, int r) { if(l > r) return 0; if(u == n) return 1; for(int i = 0; i < v[u].size(); i++) { int to = v[u][i].v; if(book[to]) continue; if(v[u][i].l <= l && v[u][i].r >= r) //这是判断能不能走到，枚举的应该是最小区间 { book[to] = 1; if(dfs(to, l, r)) return 1; } } return 0; } int main() { scanf("%d%d", &n, &m); int a, b; for(int i = 1; i <= m; i++) { scanf("%d%d%d%d", &a, &b, &L[i], &R[i]); v[a].push_back(node(b, L[i], R[i])); v[b].push_back(node(a, L[i], R[i])); } sort(L+1, L+1+m); sort(R+1, R+1+m); int ans = -1; for(int i = 1; i <= m; i++) { int l = 1, r = m+1; while(l <= r) { int mid = (l+r)/2; memset(book, 0, sizeof(book)); if(dfs(1, L[i], R[mid])) { ans = max(ans, R[mid]-L[i]+1); l = mid + 1; } else { r = mid - 1; } } } if(ans == -1) puts("Nice work, Dima!"); else printf("%d\n", ans); return 0; }