Submission #1022066

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022066		Ludissey	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	751 ms	79780 KiB

commuter_pass

#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define last(a) a[sz(a)-1]

using namespace std;

vector<vector<pair<int,int>>> neigh;
vector<pair<int,int>> two_dist;
int N,M,S,T,U,V; 
int MAXDIST=0;

void setup_twodist(){
    vector<pair<int,int>> visited(N,{false,false});
    priority_queue<pair<int,int>> pq;
    pq.push({0,S});
    two_dist[S].first=0;
    while(!pq.empty()){
        int x=pq.top().second; pq.pop();
        if(visited[x].first) continue;
        visited[x].first=true;
        for (auto u : neigh[x])
        {
            if(two_dist[u.first].first>two_dist[x].first+u.second){
                two_dist[u.first].first=two_dist[x].first+u.second;
                pq.push({-two_dist[u.first].first, u.first});
            }
        }
    }
    pq.push({0,T});
    two_dist[T].second=0;
    while(!pq.empty()){
        int x=pq.top().second; pq.pop();
        if(visited[x].second) continue;
        visited[x].second=true;
        for (auto u : neigh[x])
        {
            if(two_dist[u.first].second>two_dist[x].second+u.second){
                two_dist[u.first].second=two_dist[x].second+u.second;
                pq.push({-two_dist[u.first].second, u.first});
            }
        }
    }
    MAXDIST=two_dist[T].first;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); 
    cin >> N >> M >> S >> T >> U >> V; S--; T--; U--; V--;
    neigh.resize(N);
    two_dist.resize(N,{1e17,1e17});
    for (int i = 0; i < M; i++) 
    {
        int a,b,c; cin >> a >> b >> c;
        neigh[a-1].push_back({b-1,c});
        neigh[b-1].push_back({a-1,c});
    }
    setup_twodist();    
    vector<vector<vector<bool>>> visited(N,vector<vector<bool>>(3,vector<bool>(3,false))); // [x][direction(or none)][never been on - is on - is off]
    vector<vector<vector<int>>> dist(N,vector<vector<int>>(3,vector<int>(3,1e17))); // [x][direction(or none)][never been on - is on - is off]
    priority_queue<pair<int,pair<int,pair<int,int>>>> pq;
    pq.push({0,{U,{0,0}}});
    dist[U][0][0]=0;
    if(two_dist[U].first+two_dist[U].second==MAXDIST){ dist[U][0][1]=0; pq.push({0,{U,{0,1}}}); }

    while(!pq.empty()){
        int x=pq.top().second.first; int dir=pq.top().second.second.first; int used=pq.top().second.second.second; pq.pop();
        if(visited[x][dir][used]) continue;
        visited[x][dir][used]=true;
        for (auto u : neigh[x])
        {
            int nd=0,nu=0;
            if(used==0){
                // get off
                nd=0;
                nu=0;
                if(dist[u.first][nd][nu]>dist[x][dir][used]+u.second){
                    dist[u.first][nd][nu]=dist[x][dir][used]+u.second;
                    pq.push({-dist[u.first][nd][nu],{u.first,{nd,nu}}});
                }
                // get on
                if(two_dist[u.first].first+two_dist[u.first].second==MAXDIST){
                    nd=0;
                    nu=1;
                    if(dist[u.first][nd][nu]>dist[x][dir][used]+u.second){
                        dist[u.first][nd][nu]=dist[x][dir][used]+u.second;
                        pq.push({-dist[u.first][nd][nu],{u.first,{nd,nu}}});
                    }
                }
            } else if(used==1){
                // get off
                nd=0;
                nu=2;
                if(dist[u.first][nd][nu]>dist[x][dir][used]+u.second){
                    dist[u.first][nd][nu]=dist[x][dir][used]+u.second;
                    pq.push({-dist[u.first][nd][nu],{u.first,{nd,nu}}});
                }
                if(two_dist[u.first].first+two_dist[u.first].second==MAXDIST){
                    // continue
                    if(dir==1||dir==0){
                        if(two_dist[x].first-u.second==two_dist[u.first].first&&two_dist[x].second+u.second==two_dist[u.first].second){
                            nd=1; nu=1;
                            if(dist[u.first][nd][nu]>dist[x][dir][used]) {
                                dist[u.first][nd][nu]=dist[x][dir][used];
                                pq.push({-dist[u.first][nd][nu],{u.first,{nd,nu}}});
                            }
                        }
                    }if(dir==2||dir==0){
                        if(two_dist[x].first+u.second==two_dist[u.first].first&&two_dist[x].second-u.second==two_dist[u.first].second){
                            nd=2; nu=1;
                            if(dist[u.first][nd][nu]>dist[x][dir][used]) {
                                dist[u.first][nd][nu]=dist[x][dir][used];
                                pq.push({-dist[u.first][nd][nu],{u.first,{nd,nu}}});
                            }
                        }
                    }
                }
            } else if(used==2){
                nd=2;
                nu=2;
                if(dist[u.first][nd][nu]>dist[x][dir][used]+u.second){
                    dist[u.first][nd][nu]=dist[x][dir][used]+u.second;
                    pq.push({-dist[u.first][nd][nu],{u.first,{nd,nu}}});
                }
            }
        }
    }
    int mn=1e17;
    for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { mn=min(dist[V][i][j],mn); } }
    cout << mn << "\n";
    return 0;
}

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