Submission #351206

#	Time	Username	Problem	Language	Result	Execution time	Memory
351206		Tony1234	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	127 ms	7772 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MM = 30030, INF = 0x3f3f3f3f;
set<int> adj[MM];
int dis[MM];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> cur;
int main(){
  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  for(int i=0; i < MM; i++)dis[i] = INF;
  int num, paths, a, b; cin >> num >> paths;
  int start = -1, dest = -1;
  for(int i=0; i < paths; i++){
    cin >> a >> b;
    if(i == 0){
      start = a;
    }else if(i==1){
      dest = a;
    }
    adj[a].insert(b);
  }
  cur.push({0, start});
  dis[start] = 0;
  while(!cur.empty()){
    pii e = cur.top(); cur.pop();
    int cit = e.second, price=  e.first;
    if(cit == dest){
      cout << dis[cit]<<'\n';
      return 0;
    }
    if(dis[cit] < price)continue;
    for(int u: adj[cit]){
      //go up
      for(int i=1; cit + i*u < num; i++){
        int nn = cit+i*u;
        int add= price+i;
        if(dis[nn] > add){
            dis[nn] = add;
            cur.push({add, nn});
        }
        if(adj[nn].count(u))break;
      }
      //go down
      for(int i=1; cit-i*u >= 0; i++){
          int nn = cit-i*u;
          int add = price+i;
          if(dis[nn]>add){
          dis[nn] = add; cur.push({add, nn});
        }
        if(adj[nn].count(u))break;
      }
    }
  }
  cout << -1;
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 43 / 43