Advertisement
Josif_tepe

Untitled

Nov 2nd, 2021
148
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.26 KB | None | 0 0
  1. #include <iostream>
  2. #include<ctime>
  3. #include<map>
  4. #include<vector>
  5. #include<queue>
  6. using namespace std;
  7. vector < pair<int,int> > g[10005];
  8. bool visited[10005];
  9. int main()
  10. {
  11.     int t1,t2;
  12.     cin>>t1>>t2;
  13.     int k,n;
  14.     cin>>k>>n;
  15.    
  16.     for(int i=0;i<n;i++)
  17.     {
  18.         int a,b,c;
  19.         cin>>a>>b>>c;
  20.         g[a].push_back(make_pair(b,c));
  21.         g[b].push_back(make_pair(a,c));
  22.     }
  23.     queue <long long> q;
  24.     q.push(t1);
  25.     q.push(0);
  26.    
  27.     for(int i=0;i<=k;i++)
  28.     {
  29.         visited[i]=false;
  30.     }
  31.     while(!q.empty())
  32.     {
  33.         long long node=q.front();
  34.         q.pop();
  35.         long long dis=q.front();
  36.         q.pop();
  37.         if(node==t2)
  38.         {
  39.             cout<<llabs(dis);
  40.             return 0;
  41.         }
  42.         for(int i=0;i<g[node].size();i++)
  43.         {
  44.             int sosed=g[node][i].first;
  45.             long long d=g[node][i].second;
  46.             if(!visited[sosed])
  47.             {
  48.                visited[sosed]=true;
  49.                q.push(sosed);
  50.                if(node<sosed)
  51.                {
  52.                    q.push(dis+d);
  53.                }else
  54.                {
  55.                    q.push(dis-d);
  56.                }
  57.             }
  58.  
  59.         }
  60.     }
  61.     cout<<-1;
  62.     return 0;
  63. }
  64.  
  65.  
  66.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement