Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<stdio.h>
- #include<vector>
- #include<cmath>
- #include<algorithm>
- #include<map>
- #include<cstdlib>
- #include<cstring>
- #include <exception>
- using namespace std;
- struct Edge{
- int tBegin;
- int tEnd;
- int dst;
- };
- int main(){ freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- int n, end, m;
- cin>>n>>end>>m;
- vector<vector<Edge> > out(1 + n);
- for(int i = 0; i < m; i++){
- int len;
- cin>>len;
- int prevSt,prevT;
- cin>>prevSt>>prevT;
- for(int j = 1; j < len; j++){
- int curSt,curT;
- cin>>curSt>>curT;
- out[prevSt].push_back(Edge{prevT, curT, curSt});
- prevSt = curSt;
- prevT = curT;
- }
- }
- const int INF = 1e9 + 1;
- vector<int> d(1 + n,INF);
- d[1] = 0;
- vector<bool> u(1 + n, 0);
- while(true){
- int v = -1;
- for(int i = 1; i <= n; i++){
- if(!u[i] && (v==-1 || d[i] < d[v])){
- v = i;
- }
- }
- if(v == -1 || d[v]== INF)
- break;
- u[v] = 1;
- for(const Edge &edge : out[v]){
- if(edge.tBegin >= d[v]){
- if(edge.tEnd < d[edge.dst]){
- d[edge.dst] = edge.tEnd;
- }
- }
- }
- }
- if(d[end] == INF){
- cout<<-1;
- }
- else{
- cout<<d[end];
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement