Submission #955606

#	Time	Username	Problem	Language	Result	Execution time	Memory
955606		bunhadasou	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	262 ms	38452 KiB

commuter_pass

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define PB push_back
#define EB emplace_back
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
#define ll long long
#define sz(x) (int)x.size()
#define TASK "cf"

using namespace std;

const int maxn=1e5+5;
vector<pair<int,int>> adj[maxn];
vector<int>to[maxn],adj2[maxn],radj[maxn];
int n,m;
int s,t,ss,tt;
bool check[maxn],check2[4][maxn];
ll d[maxn],d2[4][maxn];


void dijkstra(){
    memset(check,0,sizeof(check));
    memset(d,60,sizeof(d));
    priority_queue<pair<ll,int>> pq;
    pq.push(mp(0,s));
    d[s]=0;
    while(!pq.empty()){
        int u=pq.top().se,w=pq.top().fi;
        pq.pop();
        if (check[u]) continue;
        check[u]=1;
        for (auto v:adj[u]) {
            if (d[v.fi]>d[u]+v.se) {
                to[v.fi].clear();
                to[v.fi].PB(u);
                d[v.fi]=d[u]+v.se;
                pq.push(mp(-d[v.fi],v.fi));
            }
            else if (d[v.fi]==d[u]+v.se) to[v.fi].PB(u);
        }
    }
}



signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin>>n>>m>>s>>t>>ss>>tt;

    for (int i=1;i<=m;i++) {
        int x,y,z; cin>>x>>y>>z;
        adj[x].PB(mp(y,z));
        adj[y].PB(mp(x,z));
    }

    dijkstra();
    memset(check,0,sizeof(check));
    queue<int> q;
    q.push(t);
    check[t]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        for(auto v:to[u]) {
            adj2[u].PB(v);
            radj[v].PB(u);
            if (!check[v]) {
                check[v]=1;q.push(v);
            }
        }
    }

    priority_queue<pair<ll,pair<int,int>>>pq;
    memset(d2,60,sizeof(d2));
    d2[0][ss]=0;
    pq.push(mp(0,mp(0,ss)));
    while(!pq.empty()){
        int u=pq.top().se.se,rev=pq.top().se.fi;
        ll w=pq.top().fi;pq.pop();
        if (u==tt) {cout<<d2[rev][u]<<"\n"; return 0;}
        if (check2[rev][u]) continue;
        check2[rev][u]=1;
        for (auto v:adj[u]) {
            int ne;
            if(rev==0) ne=0; else ne=3;
            if (d2[ne][v.fi]>d2[rev][u]+v.se) {
                d2[ne][v.fi]=d2[rev][u]+v.se;
                pq.push(mp(-d2[ne][v.fi],mp(ne,v.fi)));
            }
        }
        if (rev==0||rev==1) {
            for (auto v:adj2[u]) {
                if (d2[1][v]>d2[rev][u]) {
                    d2[1][v]=d2[rev][u];
                    pq.push(mp(-d2[1][v],mp(1,v)));
                }
            }
        }
        if (rev==0 || rev==2) {
            for (auto v:radj[u]){
                if (d2[2][v]>d2[rev][u]) {
                    d2[2][v]=d2[rev][u];
                    pq.push(mp(-d2[2][v],mp(2,v)));
                }
            }
        }
    }



    return 0;

}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra()':
commuter_pass.cpp:31:27: warning: unused variable 'w' [-Wunused-variable]
   31 |         int u=pq.top().se,w=pq.top().fi;
      |                           ^
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:82:12: warning: unused variable 'w' [-Wunused-variable]
   82 |         ll w=pq.top().fi;pq.pop();
      |            ^

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