Codefroces 366 D Dima and Trap Graph （最短路）

Dima and Trap Graph

题意：Dima和Inna越来越喜欢对方，但是Dima的室友缺很没有热情出去玩，然后Dima就把他室友Seryozha骗进了陷阱里。现在Seryozha想要从陷阱里出来，每条路上有一个l,r， Seryozha在走路前可以选择一个X，然后每次通过一条路的时候都需要满足条件 l <= x <= r, 每次选定了一个X之后，这个X是一个定值，不会乱变，现求这样的X的数目一共有多少，如果为0就输出“Nick work Dima!”，不然就输出数目。

题解：在每个点开一个set，存一下每次访问到这个点的时候的左区间，右区间，如果访问过了，那就不需要再走了，因为结果肯定不会比完全覆盖的更优，当然如果现在的长度已经小于等于ans的长度了，那么也不再需要再走了，就算接下来的路都不限制区间，那么也不可能比答案更优。

 #include<iostream>

 #include<vector>

 #include<set>

 #include<queue>

 #include<cstring>

 using namespace std;

 const int INF = 0x3f3f3f3f;

 const int N = 1e3+;

 typedef pair<int, int> pll;

 struct Node

 {

     int  b, l, r;

 }tmp;

 vector<Node> edge[N];

 set<pll> len[N];

 int n, m, ans = ;

 void Add_edge(int a, int b, int l, int r)

 {

     tmp.b = b;

     tmp.l = l, tmp.r = r;

     edge[a].push_back(tmp);

 }

 void solve()

 {

     queue<Node> q;

     tmp.b = , tmp.l = , tmp.r = INF;

     q.push(tmp);

     set<pll>::iterator it;

     while(!q.empty())

     {

         tmp = q.front();

         q.pop();

         int id = tmp.b;

         int l = tmp.l, r = tmp.r;

         if(id == n)

         {

             ans = max(ans, r-l+);

             continue;

         }

         if(r-l+ <= ans) continue;

         for(int i = ; i < edge[id].size(); i++)

         {

             int ll = max(l, edge[id][i].l);

             int rr = min(r, edge[id][i].r);

             int t = edge[id][i].b;

             if(ll > rr) continue;

             bool flag = ;

             for(it = len[t].begin(); it != len[t].end(); it++)

             {

                  if((*it).first <= ll && (*it).second >= rr)

                  {

                      flag = ;

                      break;

                  }

             }

             if(flag) continue;

             len[t].insert(pll(ll,rr));

             tmp.b = t;

             tmp.l = ll;

             tmp.r = rr;

             q.push(tmp);

         }

     }

 }

 int main()

 {

     ios::sync_with_stdio(false);

     cin.tie();

     cout.tie();

     int a, b, l, r;

     cin >> n >> m;

     for(int i = ; i <= m; i++)

         {

             cin >> a >> b >> l >> r;

             Add_edge(a,b,l,r);

             Add_edge(b,a,l,r);

         }

     solve();

     if(ans == ) cout << "Nice work, Dima!\n";

     else cout << ans << endl;

     return ;

 }