제출 #1202412

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1202412		ASGA_RedSea	은하철도 (APIO24_train)	C++17	0 / 100	110 ms	15548 KiB

train

/**

                                    * بسم الله الرحمن الرحيم *

                ﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿

*/

/// author : "ASGA"


#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>


using namespace std;
using ll=long long;

const ll inf=1e18;

ll solve(int n,int m,int w,vector<int>T,vector<int>X,vector<int>Y,vector<int>A,vector<int>B,vector<int>C,vector<int>L,vector<int>R){
    vector<vector<array<int,4>>>a(n);
    vector<vector<int>>b(n);
    for(int i=0;i<m;i++){
        a[X[i]].push_back({Y[i],A[i],B[i],C[i]});
        a[Y[i]].push_back({X[i],A[i],B[i],C[i]});

        b[X[i]].push_back(Y[i]);
        b[Y[i]].push_back(X[i]);
    }

    for(auto&i:a)sort(i.begin(),i.end());
    for(auto&i:b)sort(i.begin(),i.end());

    if(w==0){
        vector<int>l=L,r=R;

        vector<vector<ll>>d(n);
        for(int i=0;i<n;i++){
            for(int j=0;j<a[i].size();j++){
                d[i].push_back(inf);
            }
        }


        /// c,j,i,t;
        priority_queue<array<ll,4>,vector<array<ll,4>>,greater<array<ll,4>>>q;

        for(int j=0;j<a[0].size();j++){
            d[0][j]=a[0][j][3];
            q.push({d[0][j],a[0][j][0],0,a[0][j][2]});
        }

        ll ans=inf;

        while(!q.empty()){
            int i=q.top()[1],p=q.top()[2],t=q.top()[3];
            ll c=q.top()[0];

            q.pop();

            if(i==n-1)ans=min(ans,c);

            if(d[p][lower_bound(b[p].begin(),b[p].end(),i)-b[p].begin()]<c)continue;

            for(int j=0;j<a[i].size();j++){
                if(a[i][j][1]>=t&&c+a[i][j][3]<d[i][j]){
                    d[i][j]=c+a[i][j][3];
                    q.push({d[i][j],a[i][j][0],i,a[i][j][2]});
                }
            }
        }

        return (ans<inf?ans:-1);
    }
    else{
        ;
    }

    return -1;
}


//signed main(){
//    ios_base::sync_with_stdio(0);cin.tie(0);
//
//
//
//    return 0;
//}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60