Going to the Office – ASOCIATIA „INVESTESTE PENTRU VIITORUL TAU” BUZAU

Cerinta completa

Ms.Kox enjoys her job, but she does not like to waste extra time traveling to and from her office. After working for many years, she knows the shortest-distance route to her office on a regular day.

Recently, the city began regular maintenance of various roads. Every day a road gets blocked and no one can use it that day, but all other roads can be used. You are Ms. Kox’s new intern and she needs some help. Every day, you need to determine the minimum distance that she has to travel to reach her office.

Input Format

There are N cities numbered 0 to N-1 and M bidirectional roads.

The first line of the input contains two integers N and M.
M lines follow, each containing three space-separated integers u , v and w, where u and v are cities connected by a bi-directional road and w is the length of this road. There is at most one road between any two cities and no road connects a city to itself.
The next line contains two integers S and D. S is the city where Ms. Kox lives and D is the city where her office is located.
The next line contains an integer Q, the number of queries.
Q lines follow, each containing two integers u and v, where the road between u and v has been blocked that day.

Constraints

Output Format

Output Q lines, with each line containing the minimum distance Ms.Kox has to travel on that day. If there is no path, print “Infinity“.

Sample Input

Sample Output

Limbajul de programare folosit: cpp14

Cod:

#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <complex>
using namespace std;

// begin insert defines
#define PR pair
template<typename S, typename T> ostream& operator<<(ostream& os, pair<S,T> p){ return os << "(" << p.first << "," << p.second << ")"; };
template <class T> void PV(T x) {for(__typeof__((x).begin()) i = (x).begin(); i != (x).end(); i++) cout << *i << " "; cout << endl;}
template <class T> void PA(T x[], int n) {for (int i = 0; i < n; i++) cout << x[i] << " "; cout << endl;}
#define MP make_pair
#define forE(elem,v)  for(__typeof__(v.begin()) _it = v.begin(); _it != v.end();++_it) for(int _once=1, _done=0; _once; (!_done) ? (_it=v.end(), --_it) :_it ) for(__typeof__(*_it) & elem = * _it; _once && !(_once=0); _done=1)
typedef vector<int> VRI;
typedef pair<int, int> PII;
#define Rep(i,n) for(int n_ = (n), i = 0; i< n_; ++i)
typedef long long ll;

// end insert defines

const int N = 200010, M = 200010;
const ll INF = 1000000000000000000LL;

struct Lnk
{
  int v, next;
  ll w;
}lnk[M * 2];

int st[N], lnn;

inline void ae(int u, int v, ll w)
{
  lnk[lnn].v = v;
  lnk[lnn].w = w;
  lnk[lnn].next = st[u];
  st[u] = lnn++;
}

map<PII, ll> ans;

int n, m, bgn, mend, qn;
ll d[2][N], pre[N];
int q[N];
bool in[N];

VRI son[N];

void bfs(int bgn, int end, ll d[N])
{
  int f = 0, r = 1;
  q[f] = bgn;
  memset(in, 0, sizeof(in));
  in[bgn] = true;
  fill(d, d + n, INF);
  d[bgn] = 0;
  pre[bgn] = -1;
  for (; f < r; f++) {
    int now = q[f];
    for (int i = st[now]; i != -1; i = lnk[i].next) {
      int v = lnk[i].v;
      if (d[now] + lnk[i].w < d[v]) {
        d[v] = d[now] + lnk[i].w;
        pre[v] = now;
        if (!in[v]) {
          in[v] = true;
          q[r++] = v;
        }
      }
    }
    in[now] = false;
  }
}

bool vis[N];

struct T
{
  ll val;
  int u, v;
  friend bool operator < (const T &l, const T &r)
  {
    if (l.val != r.val) return l.val < r.val;
    if (l.u != r.u) return l.u < r.u;
    return l.v < r.v;
  }
  void as(int _u, int _v, ll _val) {
    if (_u > _v) swap(_u, _v);
    u = _u, v = _v, val = _val;
  }
};

int f, r;

set<T> can;

void bfs2(int bgn)
{
  f = 0, r = 1;
  q[f] = bgn;
  vis[bgn] = true;
  for (; f < r; f++) {
    int now = q[f];
    forE(v, son[now]) {
      if (!vis[v]) {
        vis[v] = true;
        q[r++] = v;
      }
    }
  }
}

void solve()
{
  struct T t;
  memset(vis, 0, sizeof(vis));
  Rep(i, n) if (pre[i] != -1) son[pre[i]].push_back(i);
  can.clear();
  for (int p = mend; p != bgn; p = pre[p]) {
    bfs2(p);
    Rep(j, r) {
      int now = q[j];
      for (int k = st[now]; k != -1; k = lnk[k].next) {
        int v = lnk[k].v;
        if (now == p && v == pre[p]) continue;
        ll w = lnk[k].w;
        if (vis[v]) {
          t.as(now, v, d[0][now] + d[1][v] + w);
          can.erase(t);
        }
        else {
          t.as(now, v, d[0][v] + d[1][now] + w);
          can.insert(t);
        }
      }
    }
    if (can.empty()) ans[MP(pre[p], p)] = ans[MP(p, pre[p])] = INF;
    else ans[MP(pre[p], p)] = ans[MP(p, pre[p])] = can.begin()->val;
  }
}

int main(int argc, char *argv[])
{
  scanf("%d%d", &n, &m);
  lnn = 0;
  memset(st, -1, sizeof(st));
  ans.clear();
  Rep(i, m) {
    int u, v;
    ll w;
    scanf("%d%d%lld", &u, &v, &w);
    ae(u, v, w);
    ae(v, u, w);
  }
  scanf("%d%d", &bgn, &mend);
  bfs(mend, bgn, d[1]);
  bfs(bgn, mend, d[0]);
  if (d[0][mend] == INF) {
    scanf("%d", &qn);
    Rep(qi, qn) {
      int u, v;
      scanf("%d%d", &u, &v);
      puts("Infinity");
    }
  }
  else {
    solve();
    scanf("%d", &qn);
    Rep(qi, qn) {
      int u, v;
      scanf("%d%d", &u, &v);
      ll a;
      if (ans.count(MP(u, v)))
        a = ans[MP(u, v)];
      else a = d[0][mend];
      if (a == INF) puts("Infinity");
      else printf("%lld\n", a);
    }   
  }
  return 0;
}

Scor obtinut: 1.0

Submission ID: 464650139

Link challenge: https://www.hackerrank.com/challenges/going-office/problem

Going to the Office