Submission #584692

#	Time	Username	Problem	Language	Result	Execution time	Memory
584692		FuelTheBurn	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	393 ms	24032 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

void setIO(string s) {
    ios_base::sync_with_stdio(0); cin.tie(0); 
    freopen((s+".in").c_str(),"r",stdin);
    freopen((s+".out").c_str(),"w",stdout);
}

using ll = long long;
using ld = long double;
using db = double;
using str = string;

typedef long long ll;
typedef vector<ll> vl; 
typedef vector<pair<ll,ll>> vpl; 
 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x) //will not work for bool
#define travBool(a,x) for (auto a: x)
#define print(x) trav(a,x){cout<<a<<" ";}cout<<endl; //will not work for bool
#define printBool(x) travBool(a,x){cout<<a<<" ";}cout<<endl;
#define print2d(x) trav(a,x){trav(b,a){cout<<b<<" ";}cout<<endl;}
#define doPrefixSum2d(data, prefixSum,x,y){prefixSum.resize(x,vector<ll>(y,0));F0R(i,x){prefixSum[i][0]=0;}F0R(j,y){prefixSum[0][j]=0;}FOR(i,1,x){FOR(j,1,y){prefixSum[i][j]=data[i][j]+prefixSum[i-1][j]+prefixSum[i][j-1]-prefixSum[i-1][j-1];}}}//x and y are the size of prefixSum and data including the first row of 0s
#define printQueue(q){auto copyOfQ=q;if(copyOfQ.empty()){cout<<"empty";}while(!copyOfQ.empty()){cout<<copyOfQ.front()<<" ";copyOfQ.pop();}cout<<endl;}

#define pb push_back
#define rsz resize
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define f first
#define s second

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18; // not too close to LLONG_MAX
const ld PI = acos((ld)-1);

bool ysort(const pair<ll,ll>& x, const pair<ll,ll>& y){
    return x.s<y.s;
}

ll findSum2d(vector<vector<ll>>& prefixSum,ll bx,ll by,ll ex,ll ey){
    return(prefixSum[ex][ey]-prefixSum[bx-1][ey]-prefixSum[ex][by-1]+prefixSum[bx-1][by-1]);
}//all 4 cords are inclusive

struct DSU {
    vector<int> e;
    DSU(int N) { e = vector<int>(N, -1); }

    // get representive component (uses path compression)
    int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }

    bool same_set(int a, int b) { return get(a) == get(b); }

    int size(int x) { return -e[get(x)]; }

    bool unite(int x, int y) {  // union by size, you can change this to return the new leader
        x = get(x), y = get(y);
        if (x == y) return false;
        if (e[x] > e[y]) swap(x, y);
        e[x] += e[y]; e[y] = x; return true;
    }
    void printDSU(){
        print(e);
    }
};

ll N=0;
ll M=0;
ll S=0,T=0,U=0,V=0;
ll ans=INF;
vector<vector<pair<ll,ll>>> adjList;//0 index
vector<pair<ll,pair<ll,pair<ll,ll>>>> dist;//dist,prev,least,greatest 
priority_queue<pair<ll,ll>> pq;
vector<ll> UDist;
vector<ll> VDist;
//check for fail case? is there a gaurantee of success? go re read the problem self when u feel like it

int main(){
    //setIO("fcolor");
    cin>>N;
    //cout<<"HI"<<endl;
    //cout<<N<<endl;
    cin>>M;//goes from S to T not N to M
    cin>>S;
    cin>>T;
    cin>>U;
    cin>>V;
    S--;
    T--;
    U--;
    V--;//0 index
    adjList.rsz(N);
    //dist.rsz(N,{INF,{vector<ll>(1,1),{INF,0}}});
    dist.rsz(N);
    UDist.rsz(N,INF);
    VDist.rsz(N,INF);
    trav(a,dist){
        a.f=INF;
        a.s.f=INF;
        a.s.s.f=INF;
        a.s.s.s=INF;
    }
    F0R(i,M)
    {
        ll a=0;
        ll b=0;
        ll c=0;
        cin>>a>>b>>c;
        adjList[a-1].pb({b-1,c});
        adjList[b-1].pb({a-1,c});
    }
    

    UDist[U]=0;
    pq.push({0,U});
    while(pq.size()){
        //cout<<"boom"<<endl;
        ll x=pq.top().s;
        ll d=pq.top().f;
        pq.pop();
        if(-d!=UDist[x])continue;
        trav(a,adjList[x]){
            if(UDist[a.f]>UDist[x]+a.s){
                UDist[a.f]=UDist[x]+a.s;
                pq.push({-UDist[a.f],a.f});
            }
        }
    }
    //cout<<"UDist"<<endl;
    //print(UDist);

    VDist[V]=0;
    pq.push({0,V});
    while(pq.size()){
        //cout<<"boom"<<endl;
        ll x=pq.top().s;
        //cout<<x<<endl;
        ll d=pq.top().f;
        pq.pop();
        if(-d!=VDist[x])continue;
        trav(a,adjList[x]){
            if(VDist[a.f]>VDist[x]+a.s){
                VDist[a.f]=VDist[x]+a.s;
                pq.push({-VDist[a.f],a.f});
            }
        }
    }

    //cout<<"VDist"<<endl;
    //print(VDist);
    dist[S]={0,{UDist[S]+VDist[S],{UDist[S],VDist[S]}}};
    pq.push({0,S});
    while(pq.size()){

        ll x=pq.top().s;
        ll d=pq.top().f;
        pq.pop();
        if(-d!=dist[x].f)continue;
        //cout<<"x: "<<x<<endl;
        trav(a,adjList[x]){
            if(dist[a.f].f>=dist[x].f+a.s){
                if(dist[a.f].f==dist[x].f+a.s){
                    
                    dist[a.f].s.s.f=min(UDist[a.f],min(dist[x].s.s.f,dist[a.f].s.s.f));
                    dist[a.f].s.s.s=min(VDist[a.f],min(dist[x].s.s.s,dist[a.f].s.s.s));
                    dist[a.f].s.f=min(min(dist[x].s.f,dist[a.f].s.f),min(dist[a.f].s.s.f+VDist[a.f],dist[a.f].s.s.s+UDist[a.f]));
                }//fix this

                else{
                    dist[a.f].f=dist[x].f+a.s;
                    dist[a.f].s.s.f=min(UDist[a.f],dist[x].s.s.f);
                    dist[a.f].s.s.s=min(VDist[a.f],dist[x].s.s.s);
                    dist[a.f].s.f=min(dist[x].s.f,min(dist[a.f].s.s.f+VDist[a.f],dist[a.f].s.s.s+UDist[a.f]));
                    pq.push({-dist[a.f].f,a.f});
                }
            }
        }
    }
    /*
    //print(dist);
    cout<<"shortest"<<endl;
    cout<<dist[T].f<<endl;
    cout<<"ans"<<endl;
    cout<<dist[T].s.f<<endl;
    cout<<"leastStops"<<endl;
    cout<<dist[T].s.s.f<<endl;
    cout<<"mostStops"<<endl;
    cout<<dist[T].s.s.s<<endl;
    */
    cout<<min(dist[T].s.f,UDist[V])<<endl;
    /*
    cout<<"test"<<endl;
    F0R(i,N){
        cout<<"i: "<<i<<endl;
        cout<<"shortest: ";
        cout<<dist[i].f<<endl;
        cout<<"ans: ";
        cout<<dist[i].s.f<<endl;
        cout<<"leastStops: ";
        cout<<dist[i].s.s.f<<endl;
        cout<<"mostStops: ";
        cout<<dist[i].s.s.s<<endl;        
    }
    //acount for case where u just skip the S to T
    

    cout<<"adjList"<<endl;
    trav(a,adjList){trav(b,a){cout<<"{"<<b.f<<" "<<b.s<<"}"<<" ";}cout<<endl;}
    cout<<"test stuff"<<endl;
    
    cout<<dist[4].s.f<<endl;
    cout<<dist[5].s.f<<endl;
    cout<<dist[6].s.f<<endl;
    cout<<dist[7].s.f<<endl;    
    
    F0R(i,N){
        cout<<i<<" "<<dist[i].s.f<<endl;
    }
    */

}

Compilation message (stderr)

commuter_pass.cpp: In function 'void setIO(std::string)':
commuter_pass.cpp:6:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 |     freopen((s+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:7:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |     freopen((s+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45