daily pastebin goal
0%
SHARE
TWEET

X19647 - Cheapest Routes

sr_pope Jan 17th, 2019 138 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <vector>
  2. #include <iostream>
  3. #include <queue>
  4. using namespace std;
  5.  
  6. typedef pair<int,int> arc;
  7.  
  8. void route(const vector<int>& hotel, const vector<vector<arc> >& g, int x, int y){
  9.     int n = g.size();
  10.     vector<bool> visited(n,false);
  11.     vector<int> p(n,100001);
  12.     priority_queue <arc,vector<arc>, greater<arc> > PC;
  13.     PC.push(arc(0,x));
  14.     p[x] = 0;
  15.     while(!PC.empty() && !visited[y]){
  16.         arc a = PC.top();
  17.         int u = a.second;
  18.         PC.pop();
  19.         if(!visited[u]){
  20.             visited[u] = true;
  21.             for(int i = 0; i < g[u].size(); ++i){
  22.                 arc b = g[u][i];
  23.                 int v = b.second;
  24.                 int w = b.first;
  25.                 if(!visited[v]){
  26.                     if(p[v] > p[u] + w + hotel[v]){
  27.                         p[v] = p[u] + w + hotel[v];
  28.                     }
  29.                     PC.push(arc(p[v],v));
  30.                 }
  31.             }
  32.         }
  33.         //cout << u;
  34.     }
  35.     if(p[y] == 100001) cout << "c(" << x << "," << y << ") = +oo" << endl;
  36.     else cout << "c(" << x << "," << y << ") = " << p[y] - hotel[y] << endl;
  37. }
  38.  
  39. int main(){
  40.     int n,m;
  41.     cin >> n >> m;
  42.     vector<int> hotel(n);
  43.     for(int i = 0; i < n; ++i) cin >> hotel[i];
  44.     vector<vector<arc> > g(n);
  45.     for(int i = 0; i < m; ++i){
  46.         int u,v,w;
  47.         cin >> u >> v >> w;
  48.         g[u].push_back(arc(w,v));
  49.         g[v].push_back(arc(w,u));
  50.     }
  51.     int x,y;
  52.     while(cin >> x >> y){
  53.         if(x == y) cout << "c(" << x << "," << y << ") = 0" << endl;
  54.         else route(hotel,g,x,y);
  55.     }
  56. }
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