Submission #1287893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287893		minhpk	Olympic Bus (JOI20_ho_t4)	C++20	37 / 100	1100 ms	102304 KiB

ho_t4

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b;
struct node{
      int x,w,id;
      bool operator<(const node &o) const {
        if (x != o.x) return x < o.x;
        if (w != o.w) return w < o.w;
        return id < o.id;
     }
};
multiset <node> z[1000005];
multiset <node> z1[1000005];
bool check[1000005];
int cnt[100005][5];
int bruh=1e16;
pair<int,int> trace[1000005];
void dijkstra(int sta,int fin,int id){
    for (int i=1;i<=a;i++){
         cnt[i][id]=bruh;
    }
    for (int i=1;i<=a;i++){
         trace[i]={0,0};
    }
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
    q.push({0,sta});
    cnt[sta][id]=0;
    while (q.size()){
          pair<int,int> pos=q.top();
          q.pop();
          int val=pos.first;
          int pos1=pos.second;

          if (val>cnt[pos1][id]){
              continue;
          }
          if (id<=1){
              for (auto [p,w,nxt]:z[pos1]){
               if (cnt[p][id]>val+w){
                   cnt[p][id]=val+w;
                   trace[p]={pos1,nxt};
                   q.push({cnt[p][id],p});
               }
            }
          }else{
             for (auto [p,w,nxt]:z1[pos1]){
               if (cnt[p][id]>val+w){
                   cnt[p][id]=val+w;
                   trace[p]={pos1,nxt};
                   q.push({cnt[p][id],p});
               }
            }
          }
    }
    if (id<=1){
        for (int i=fin;i!=sta && i!=0;i=trace[i].first){
             check[trace[i].second]=true;
        }
    }
}
struct edge{
      int x,y,w,d;
};
edge sad[1000005];
int cnt1[1000005];
int dijkstra1(int sta,int fin){
    for (int i=1;i<=a;i++){
         cnt1[i]=bruh;
    }
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
    q.push({0,sta});
    cnt1[sta]=0;
    while (q.size()){
         auto [val,pos]=q.top();
         q.pop();
         if (val>cnt1[pos]){
             continue;
         }
         for (auto [p,w,id]:z[pos]){
              if (cnt1[p]>val+w){
                  cnt1[p]=val+w;
                  q.push({cnt1[p],p});
              }
         }
    }
    return cnt1[fin];
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b;
    for (int i=1;i<=b;i++){
         int x,y,w,d;
         cin >> x >> y >> w >> d;
         z[x].insert({y,w,i});
         z1[y].insert({x,w,i});
         sad[i]={x,y,w,d};
    }
    dijkstra(1,a,0);
    dijkstra(a,1,1);
    dijkstra(1,a,2);
    dijkstra(a,1,3);
    int min1=min(cnt[a][0]+cnt[1][1],bruh);
    for (int i=1;i<=b;i++){
         auto [u,v,w,d]=sad[i];
         if (check[i]){
             auto it=z[u].find({v,w,i});
             z[u].erase(it);
             z[v].insert({u,w,i});
             min1=min(min1,dijkstra1(1,a)+dijkstra1(a,1)+d);
              it=z[v].find({u,w,i});
             z[v].erase(it);
             z[u].insert({v,w,i});
         }else{
             min1=min(min1,min(cnt[v][0]+w+cnt[u][3],cnt[a][0])+min(cnt[v][1]+cnt[u][2]+w,cnt[1][1]) +d);
         }
    }
    if (min1==bruh){
         cout << -1 << "\n";
         return 0;
    }
    cout << min1 << "\n";
//    cout << cnt[3][0]+cnt[5][3]+89 << "\n";
//    if (min1==bruh){
//        cout << -1 << "\n";
//    }else{
//        cout << min1 << "\n";
//    }
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 0 / 63