fork download
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3. #define PRECISION 0
  4. using namespace std;
  5. using ll = long long;
  6. #define fr first
  7. #define sc second
  8. using pl2 = pair<ll, ll>;
  9.  
  10. const ll INF = 0x3f3f3f3f3f3f3f3f;
  11.  
  12. bool chk[100020];
  13. vector<pl2> adj[100020];
  14. ll dis[100020];
  15.  
  16. void Main(){
  17. int n, m; n = 100000; m = 299993; // cin >> n >> m;
  18. //for (int i = 0; i < n; i++){ cin >> chk[i]; } chk[n-1] = 0;
  19. for (int i = 2; i <= n-2; i++){ // n-3
  20. int v, w, x; v = 0; w = i; x = 1; //cin >> v >> w >> x;
  21. adj[v].push_back({w, x}); adj[w].push_back({v, x});
  22. }
  23. for (int i = 2; i <= n-2; i++){ // n-3
  24. int v, w, x; v = i; w = 1; x = 100000-i; //cin >> v >> w >> x;
  25. adj[v].push_back({w, x}); adj[w].push_back({v, x});
  26. }
  27. for (int i = 1; i <= n-1; i++){ // n-1
  28. int v, w, x; v = 1; w = i; x = 100000; //cin >> v >> w >> x;
  29. if (w == 1){ w = 0; }
  30. adj[v].push_back({w, x}); adj[w].push_back({v, x});
  31. }
  32. memset(dis, 0x3f, sizeof(dis)); dis[0] = 0;
  33. priority_queue< pl2, vector<pl2>, greater<pl2> > pq; pq.push({0, 0});
  34. while (!pq.empty()){
  35. int now = pq.top().fr; ll dst = pq.top().sc;
  36. pq.pop();
  37. if (dis[now] != dst){ continue; }
  38. for (pl2 p : adj[now]){
  39. int nxt = p.fr; ll d = p.sc;
  40. if (chk[nxt]){ continue; }
  41. if (dis[nxt] <= dst+d){ continue; }
  42. pq.push({nxt, dst+d}); dis[nxt] = dst+d;
  43. }
  44. }
  45. if (dis[n-1] == INF){ cout << -1; } else{ cout << dis[n-1]; }
  46. }
  47.  
  48. int main(){
  49. ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  50. cout.setf(ios::fixed); cout.precision(PRECISION);
  51. Main();
  52. }
Time limit exceeded #stdin #stdout 5s 23204KB
stdin
Standard input is empty
stdout
Standard output is empty