Guest User

Untitled

a guest
Oct 19th, 2017
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.13 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. class nameclass{
  6.     public:
  7.         bool operator()(int &a, int &b){
  8.             return a>b;
  9.         }
  10. };
  11.  
  12. struct scale{
  13.     int f;
  14.     int s;
  15.     int t;
  16. };
  17.  
  18. vector<scale> g[1000000];
  19. long long int dist[10000000];
  20. priority_queue<int, vector<int>, nameclass> pq;
  21. scale P;
  22.  
  23. void Dijkstra(){
  24.     pq.push(0);
  25.     dist[0]=0;
  26.     while(!pq.empty()){
  27.         int h=pq.top();
  28.         pq.pop();
  29.         for(int x=0; x<g[h].size(); x++){
  30.             if(g[h][x].s<=dist[h] && g[h][x].t>=dist[h]+1){
  31.                 if(dist[g[h][x].f]==-1 || dist[h]+1<dist[g[h][x].f]){
  32.                     dist[g[h][x].f]=dist[h]+1;
  33.                     pq.push(g[h][x].f);
  34.                     continue;
  35.                 }
  36.             }
  37.             if(g[h][x].s>dist[h]){
  38.                 if(dist[g[h][x].f]==-1 || g[h][x].s+1<dist[g[h][x].f]){
  39.                     dist[g[h][x].f]=g[h][x].s+1;
  40.                     pq.push(g[h][x].f);
  41.                 }
  42.             }
  43.         }
  44.     }
  45. }
  46.  
  47. int raggiungi(int N, int M, int A[], int B[], int inizio[], int fine[]) {
  48.     for(int x=0; x<M; x++){
  49.         P.f=B[x];
  50.         P.s=inizio[x];
  51.         P.t=fine[x];
  52.         g[A[x]].push_back(P);
  53.         P.f=A[x];
  54.         P.s=inizio[x];
  55.         P.t=fine[x];
  56.         g[B[x]].push_back(P);
  57.     }
  58.     for(int x=0; x<N; x++){
  59.         dist[x]=-1;
  60.     }
  61.     Dijkstra();
  62.     return dist[N-1];
  63. }
Add Comment
Please, Sign In to add comment