fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define maxn 100005
  7. #define FOR(i , a , b) for(int i = a ; i <= b; i++)
  8. #define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  9. #define pll pair<ll,ll>
  10. #define fi first
  11. #define se second
  12.  
  13. int n , m , p , U[maxn] , V[maxn] , ans[3 * maxn] , M;
  14.  
  15. ll bit[3 * maxn];
  16.  
  17. void update(int idx , ll val){
  18.     while(idx <= 2 * M){
  19.         bit[idx] += val;
  20.         idx += idx & (-idx);
  21.     }
  22. }
  23.  
  24. ll get(int idx){
  25.     ll sum = 0;
  26.     while(idx > 0){
  27.         sum += bit[idx];
  28.         idx -= idx & (-idx);
  29.     }
  30.     return sum;
  31. }
  32.  
  33. struct Edge{
  34.     int v;
  35.     ll w;
  36.     int id;
  37. };
  38.  
  39. struct State{
  40.     ll dist;
  41.     int node;
  42.     bool operator > (const State &other) const{
  43.         return dist > other.dist;
  44.     }
  45. };
  46.  
  47. struct Nanh_cuti{
  48.     ll a , b , orga , orgb;
  49.     int id;
  50. };
  51.  
  52. vector<Edge> adj[maxn];
  53.  
  54. const ll INF = 1e18;
  55.  
  56. vector<ll> dijkstra(int s){
  57.     vector<ll> d(n + 1 , INF);
  58.     priority_queue<State , vector<State> , greater<State>> q;
  59.     d[s] = 0;
  60.     q.push({d[s] , s});
  61.     while(!q.empty()){
  62.         State cur = q.top();
  63.         q.pop();
  64.         ll kc = cur.dist;
  65.         int u = cur.node;
  66.  
  67.         if(kc > d[u]) continue;
  68.  
  69.         for(auto &x : adj[u]){
  70.             int v = x.v;
  71.             ll w = x.w;
  72.             if(d[v] > d[u] + w){
  73.                 d[v] = d[u] + w;
  74.                 q.push({d[v] , v}); 
  75.             }
  76.         }
  77.     }
  78.     return d;
  79. }
  80.  
  81. int getd2id(const vector<ll> &allD2 , ll x){
  82.     return upper_bound(allD2.begin() ,allD2.end() , x) - allD2.begin() + 1;
  83. }
  84.  
  85. bool cmp(pll &a , pll &b){
  86.     return a.fi < b.fi;
  87. }
  88.  
  89. bool cmp2(Nanh_cuti &c , Nanh_cuti &d){
  90.     return c.a < d.a;
  91. }
  92.  
  93. int main(){
  94.     if(fopen("IMPEVAL.INP" , "r")){
  95.         freopen("IMPEVAL.INP" , "r" , stdin);
  96.         freopen("IMPEVAL.OUT" , "w" , stdout);
  97.     }
  98.  
  99.     FAST;
  100.     cin >> n >> m >> p;
  101.     FOR(i , 1 , m){
  102.         ll w;
  103.         cin >> U[i] >> V[i] >> w;
  104.         adj[U[i]].push_back({V[i] , w , i});
  105.         adj[V[i]].push_back({U[i] , w , i});
  106.     }
  107.  
  108.     vector<ll> d1 = dijkstra(1);
  109.     vector<ll> d2 = dijkstra(2);
  110.  
  111.     vector<Nanh_cuti> queries;
  112.     queries.reserve(2 * p);
  113.  
  114.     FOR(j , 0 , p - 1){
  115.         int t;
  116.         ll w;
  117.         cin >> t >> w;
  118.         int u = U[t];
  119.         int v = V[t];
  120.         ll new_d1u = min(d1[u] , d1[v] + w);
  121.         ll new_d1v = min(d1[v] , d1[u] + w);
  122.         ll new_d2u = min(d2[u] , d2[v] + w);
  123.         ll new_d2v = min(d2[v] , d2[u] + w);
  124.         queries.push_back({new_d1u , new_d2u , d1[u] , d2[u] , j * 2});
  125.         queries.push_back({new_d1v , new_d2v , d1[v] , d2[v] , 2 * j + 1});
  126.     }
  127.     vector<ll> allD2;
  128.  
  129.     FOR(i , 1 , n) allD2.push_back(d2[i]);
  130.     FOR(i , 0 , 2 * p - 1) allD2.push_back(queries[i].b);
  131.  
  132.     sort(allD2.begin() , allD2.end());
  133.     allD2.erase(unique(allD2.begin() , allD2.end()) , allD2.end());
  134.     M = allD2.size();
  135.  
  136.     vector<pll> pts(n);
  137.     FOR(i , 0 , n - 1){
  138.         pts[i] = {d1[i + 1] , d2[i + 1]};
  139.     }
  140.  
  141.     sort(pts.begin() , pts.end() , cmp);
  142.     sort(queries.begin() ,queries.end() , cmp2);
  143.  
  144.  
  145.     vector<int> compPt;
  146.     compPt.reserve(n);
  147.     vector<int> compQ;
  148.     compQ.reserve(2 * p);
  149.  
  150.     FOR(i , 0 , n - 1) compPt.push_back(getd2id(allD2 , pts[i].second));
  151.     for(auto &q : queries) compQ.push_back(getd2id(allD2 , q.b));
  152.  
  153.     int j = 0;
  154.     FOR(i , 0 , (int) queries.size() - 1){
  155.         while(j < n && pts[j].fi <= queries[i].a){
  156.             update(compPt[j] , 1);
  157.             j++;
  158.         }
  159.  
  160.         int cnt = get(compQ[i]);
  161.         if(queries[i].orga > queries[i].a || queries[i].orgb > queries[i].b) ++cnt;
  162.         ans[queries[i].id] = cnt;
  163.     }
  164.  
  165.     FOR(j , 0 , p - 1) cout << ans[2 * j] << " " << ans[2 * j + 1] << "\n";
  166. }
  167.  
Success #stdin #stdout 0.01s 10028KB
comments (?)
stdin
copy 
5 6 2
1 5 8
5 2 10
1 3 6
3 2 12
3 4 3
4 2 11
5 2
6 9
stdout
copy 
1 2
1 1
https://ideone.com/PlnY8R
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!