SHARE
TWEET

TollRoads

a53 May 19th, 2019 91 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. ifstream in("tollroads.in");
  4. ofstream out("tollroads.out");
  5. const int Max=100005;
  6. vector < pair <int , int > >v[Max];
  7. int d[Max],n,m,q;
  8. vector < int >c[Max];
  9.  
  10. void citire()
  11. {
  12.   in>>n>>m>>q;
  13.   for(int i=1;i<=m;i++)
  14.   {
  15.       int x,y,z; in>>x>>y>>z;
  16.       v[x].push_back({y,z});
  17.       v[y].push_back({x,z});
  18.   }
  19. }
  20. int Dijkstra(int nodd,int dist)
  21. {
  22.      c[0].push_back(nodd);
  23.      for(int i=1;i<=n;i++)
  24.         d[i]=dist+1;
  25.         d[nodd]=0;
  26.     for(int t=0;t<dist;t++)
  27.     {
  28.         for(int i=0;i<c[t].size();i++)
  29.             if(d[c[t][i]]==t)
  30.         {
  31.             for(int j=0;j<v[c[t][i]].size();j++)
  32.             {
  33.                 int vecin=v[c[t][i]][j].first;
  34.                 int cost=v[c[t][i]][j].second;
  35.                 if(d[vecin]>d[c[t][i]]+cost)
  36.                 {
  37.                     d[vecin]=d[c[t][i]]+cost;
  38.                     c[d[vecin]].push_back(vecin);
  39.                 }
  40.             }
  41.         }
  42.         c[t].clear();
  43.     }
  44.     c[dist].clear();
  45.      int nr=0;
  46.      for(int i=1;i<=n;i++)
  47.         if(i!=nodd && d[i]<=dist)
  48.         nr++;
  49.      return nr;
  50. }
  51. int main()
  52. {
  53.     citire();
  54.    for(int i=1;i<=q;i++)
  55.    {
  56.        int x,y; in>>x>>y;
  57.        out<<Dijkstra(x,y)<<"\n";
  58.    }
  59.     return 0;
  60. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top