Advertisement
Josif_tepe

Untitled

Feb 13th, 2024
685
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.03 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int maxn = 1e5 + 10;
  5. const int INF = (1 << 30);
  6. typedef long long ll;
  7. const ll inf = (1LL << 59LL);
  8. struct node{
  9.     int till, euro, time;
  10.     node (){}
  11.     node(int _t, int _timee, int _e){
  12.         till = _t;
  13.         time = _timee;
  14.         euro = _e;
  15.     }
  16. };
  17. vector<node> graph[5005];
  18. int n, m, S;
  19. bool visited[3005][6005];
  20. int idx[3005];
  21. int main()
  22. {
  23.     ios_base::sync_with_stdio(false);
  24.     cin >> S >> n >> m;
  25.     for(int i = 0; i < m; i++){
  26.         int a, b, c, d;
  27.         cin >> a >> b >> c >> d;
  28.         a--; b--;
  29.         graph[a].push_back(node(b, c, d));
  30.         graph[b].push_back(node(a, c, d));
  31.     }
  32.     memset(visited, false, sizeof visited);
  33.    int  min_vreme = INF;
  34.     queue<int> q;
  35.     q.push(0);
  36.     q.push(0);
  37.     q.push(0);
  38.     int sosed;
  39.     int weight, money;
  40.     int eee;
  41.     while(!q.empty()){
  42.         int teme = q.front();
  43.         q.pop();
  44.         int pari = q.front();
  45.         q.pop();
  46.         int pat = q.front();
  47.         q.pop();
  48.         if(teme == n - 1){
  49.             if(pat <= S){
  50.                 min_vreme = min(min_vreme, pari);
  51.             }
  52.             continue;
  53.         }
  54.         for(int i = 0; i < (int)graph[teme].size(); i++){
  55.             sosed = graph[teme][i].till;
  56.             money = graph[teme][i].time;
  57.             weight = graph[teme][i].euro;
  58.             if(weight + pat <= S){
  59.                     eee = money + pari;
  60.             if(eee >= 6000) eee -= 6000;
  61.                 if(!visited[sosed][eee]){
  62.                     visited[sosed][eee] = true;
  63.                     q.push(sosed);
  64.                     q.push(pari + money);
  65.                     q.push(pat + weight);
  66.                 }
  67.             }
  68.         }
  69.  
  70.     }
  71.  
  72.     q.push(0);
  73.     q.push(0);
  74.     q.push(0);
  75.     memset(visited, false, sizeof visited);
  76.     while(!q.empty()){
  77.         int teme = q.front();
  78.         q.pop();
  79.         int pari = q.front();
  80.         q.pop();
  81.         int pat = q.front();
  82.         q.pop();
  83.         if(teme == n - 1){
  84.             if(pat <= S){
  85.                 min_vreme = min(min_vreme, pari);
  86.             }
  87.             continue;
  88.         }
  89.         for(int i = 0; i < (int)graph[teme].size(); i++){
  90.             sosed = graph[teme][i].till;
  91.             money = graph[teme][i].time;
  92.             weight = graph[teme][i].euro;
  93.             if(weight + pat <= S){
  94.                     eee = pat + weight;
  95.                 if(eee >= 6000){
  96.                     eee -= 6000;
  97.                 }
  98.                 if(!visited[sosed][pat + weight]){
  99.                     visited[sosed][pat + weight] = true;
  100.                     q.push(sosed);
  101.                     q.push(pari + money);
  102.                     q.push(pat + weight);
  103.                 }
  104.             }
  105.         }
  106.  
  107.     }
  108.         q.push(0);
  109.     q.push(0);
  110.     q.push(0);
  111.     memset(idx, 0, sizeof idx);
  112.     memset(visited, false, sizeof visited);
  113.     while(!q.empty()){
  114.         int teme = q.front();
  115.         q.pop();
  116.         int pari = q.front();
  117.         q.pop();
  118.         int pat = q.front();
  119.         q.pop();
  120.         if(teme == n - 1){
  121.             if(pat <= S){
  122.                 min_vreme = min(min_vreme, pari);
  123.             }
  124.             continue;
  125.         }
  126.         for(int i = 0; i < (int)graph[teme].size(); i++){
  127.             sosed = graph[teme][i].till;
  128.             money = graph[teme][i].time;
  129.             weight = graph[teme][i].euro;
  130.             if(weight + pat <= S){
  131.                     eee = idx[sosed] + 1;
  132.                     if(eee >= 6000){
  133.                         eee -= 6000;
  134.                     }
  135.                     idx[sosed]++;
  136.                 if(!visited[sosed][pat + weight]){
  137.                     visited[sosed][pat + weight] = true;
  138.                     q.push(sosed);
  139.                     q.push(pari + money);
  140.                     q.push(pat + weight);
  141.                 }
  142.             }
  143.         }
  144.  
  145.     }
  146.  
  147.  
  148.  
  149.     if(min_vreme == INF){
  150.         cout << -1 << endl;
  151.         return 0;
  152.     }
  153.     cout << min_vreme << endl;
  154.     return 0;
  155. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement