Submission #118019

#	Time	Username	Problem	Language	Result	Execution time	Memory
118019		JohnTitor	Commuter Pass (JOI18_commuter_pass)	C++11	100 / 100	710 ms	23648 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
#define __builtin_popcount __builtin_popcountll
using ll=long long; using ld=long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2;
template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);}
template <typename T> inline void writeln(T x){write(x); putchar('\n');}
#define taskname "Commuter"
int n, m;
int s, t, u, v;
class edge{
public:
    int a, b, c, x;
    bool good;
    void input(){
        read(a);
        read(b);
        read(c);
        x=a^b;
        good=0;
    }
} e[200001];
vector <int> g[100001];
ll f[100001];
ll d[100001][3];
class cmp{
public:
    bool operator ()(pair <int, ll> A, pair <int, ll> B){
        return A.second>B.second;
    }
};
priority_queue <pair <int, ll>, vector <pair <int, ll>>, cmp> q;
void dij(int a){
    FOR(i, 1, n) f[i]=1e18;
    while(!q.empty()) q.pop();
    q.push(mp(a, 0));
    f[a]=0;
    while(!q.empty()){
        pair <int, ll> p=q.top();
        q.pop();
        if(f[p.first]<p.second) continue;
        for(int i: g[p.first]){
            int v=e[i].x^p.first;
            int cost=e[i].c;
            if(f[v]>p.second+cost){
                f[v]=p.second+cost;
                q.push(mp(v, f[v]));
            }
        }
    }
}
class cmp2{
public:
    bool operator ()(pair <pair <int, int>, ll> A, pair <pair <int, int>, ll> B){
        return A.second>B.second;
    }
};
priority_queue <pair <pair <int, int>, ll>, vector <pair <pair <int, int>, ll>>, cmp2> q2;
void dij2(int a){
    FOR(i, 1, n) FOR(j, 0, 2) d[i][j]=1e18;
    while(!q2.empty()) q2.pop();
    q2.push(mp(mp(a, 0), 0));
    d[a][0]=0;
    while(!q2.empty()){
        pair <pair <int, int>, ll> p=q2.top();
        q2.pop();
        if(d[p.first.first][p.first.second]<p.second) continue;
//        cerr<<p.first.first<<' '<<p.first.second<<' '<<p.second<<'\n';
        for(int i: g[p.first.first]){
            int v=e[i].x^p.first.first;
            int cost=e[i].c;
            if((p.first.second<=1)&&e[i].good&&(p.first.first==e[i].a)) cost=0;
            int nx=(cost==0);
            if(nx!=1) if(p.first.second) nx=2;
            if(d[v][nx]>p.second+cost){
                d[v][nx]=p.second+cost;
                q2.push(mp(mp(v, nx), d[v][nx]));
            }
        }
    }
}
bool done[100001];
void mark(){
    queue <int> q;
    q.push(t);
    done[t]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i: g[u]){
            int v=e[i].x^u;
            if(f[v]+e[i].c==f[u]){
                e[i].good=1;
                if(e[i].a!=v) swap(e[i].a, e[i].b);
                if(!done[v]){
                    done[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
int main(){
    #ifdef Aria
        if(fopen(taskname".in", "r"))
            freopen(taskname".in", "r", stdin);
    #endif // Aria
    read(n);
    read(m);
    read(s);
    read(t);
    read(u);
    read(v);
    FOR(i, 1, m){
        e[i].input();
        g[e[i].a].pb(i);
        g[e[i].b].pb(i);
    }
    dij(s);
    mark();
    dij2(u);
    ll ans=min(d[v][0], min(d[v][1], d[v][2]));
    dij2(v);
    ans=min(ans, min(d[u][0], min(d[u][1], d[u][2])));
    writeln(ans);
}

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