Advertisement
Guest User

Untitled

a guest
Jun 22nd, 2018
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.44 KB | None | 0 0
  1.  
  2. #include<iostream>
  3. #include<stdio.h>
  4. #include<vector>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<map>
  8. #include<cstdlib>
  9. #include<cstring>
  10. #include <exception>
  11.  
  12. using namespace std;
  13.  
  14. struct Edge{
  15.     int tBegin;
  16.     int tEnd;
  17.     int dst;
  18. };
  19.  
  20. int main(){ freopen("input.txt", "r", stdin);
  21.     freopen("output.txt", "w", stdout);
  22.     int n, end, m;
  23.     cin>>n>>end>>m;
  24.     vector<vector<Edge> > out(1 + n);
  25.     for(int i = 0; i < m; i++){
  26.         int len;
  27.         cin>>len;
  28.         int prevSt,prevT;
  29.         cin>>prevSt>>prevT;
  30.         for(int j = 1; j < len; j++){
  31.             int curSt,curT;
  32.             cin>>curSt>>curT;
  33.             out[prevSt].push_back(Edge{prevT, curT, curSt});
  34.             prevSt = curSt;
  35.             prevT = curT;
  36.         }
  37.     }
  38.     const int INF = 1e9 + 1;
  39.     vector<int> d(1 + n,INF);
  40.     d[1] = 0;
  41.     vector<bool> u(1 + n, 0);
  42.     while(true){
  43.         int v = -1;
  44.         for(int i = 1; i <= n; i++){
  45.             if(!u[i] && (v==-1 || d[i] < d[v])){
  46.                 v = i;
  47.             }
  48.         }
  49.         if(v == -1 || d[v]== INF)
  50.             break;
  51.         u[v] = 1;
  52.         for(const Edge &edge : out[v]){
  53.             if(edge.tBegin >= d[v]){
  54.                 if(edge.tEnd < d[edge.dst]){
  55.                     d[edge.dst] = edge.tEnd;
  56.                 }
  57.             }
  58.         }
  59.     }
  60.     if(d[end] == INF){
  61.         cout<<-1;
  62.     }
  63.     else{
  64.         cout<<d[end];
  65.     }
  66.     return 0;
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement