Submission #870411

#	Time	Username	Problem	Language	Result	Execution time	Memory
870411		dappy	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	362 ms	262144 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

// Types
typedef long long ll;
typedef string str;

typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<char> vc;
template <class T> using V = vector<T>;
template <class T, class E> using PR = pair<T, E>;

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

typedef set<ll> sll;
typedef map<ll, ll> mll;

typedef priority_queue<pll, V<pll>, greater<pll>> pqll;

#define umap unordered_map
#define uset unordered_set

// Firsts
#define FAST cin.tie(0); cout.tie(0); ios::sync_with_stdio(0)
#define READ_FILE(i, o) freopen(i, "r", stdin); freopen(o, "w", stdout)
#define PRECISION(n) cout << fixed << setprecision(n)

// Pair
#define MP make_pair
#define F first
#define S second

// For
#define rep(i,n) for (ll i = 0; i < (n); i++)
#define repOnto(i,n) for (ll i = 1; i < (n); i++)
#define per(i,n) for (ll i = (n)-1; i >= 0; i--)
#define loop(i,s,n,in) for (ll i = (s); i < (n); i+=(in))
#define pool(i,s,n,de) for (ll i = (n)-1; i >= (s); i-=(de))
#define each(e,v) for(auto &e : v)

// Input
#define gets(val) cin >> val
template <class T> void get(T &t) {
    cin >> t;
}
template <class T, class... U> void get(T &t, U &... u) {
    get(t); get(u...);
}
template <class T> void get(V<T> &v) {
    each(e, v) get(e);
}

// Output
#define puts(val) cout << val << "\n"
template <class T> void put(T &t) {
    cout << t;
}
template <class T, class... U> void put(T &t, U &... u) {
    put(t); put(u...);
}

#define NXT "\n"
#define SB " "
#define nxt() cout << "\n"
#define sp() cout << " "
#define yes() cout << "YES\n";
#define no() cout << "NO\n";

// Extras
#define all(v) (v).begin(), (v).end()
#define sz(x) ((ll) ((x).size()))

#define PB push_back
#define P push
#define I insert

const double eps = 1e-9;
const ll INF = 1e16;
const ll MOD = 1e9 + 7;

void solve() {
    ll n,m; get(n,m);

    ll s,t; get(s,t);
    s--; t--;

    ll u,v; get(u,v);
    u--; v--;

    V<V<pll>> adj(n);

    ll a,b,c;
    rep(i,m){
        get(a,b,c);
        a--;b--;
        adj[a].PB(MP(b,c));
        adj[b].PB(MP(a,c));
    }

    pqll pq;

    pq.P(MP(s,0));

    vll dist(n, INF);

    ll node, distance;
    while(!pq.empty()){
        tie(distance, node) = pq.top();
        pq.pop();

        if(dist[node] <= distance) continue;

        dist[node] = distance;

        each(e, adj[node]){
            pq.P(MP(distance+e.second, e.first));
        }
    }


    V<V<bool>> saved(n, V<bool>(n, false));

    queue<ll> que;

    V<bool> vis(n, 0);

    que.P(t);

    while (sz(que)) {
        ll v = que.front();
        que.pop();
        ll d = dist[v];

        if (vis[v]) continue;
        vis[v] = 1;

        each(p, adj[v]){
            ll u, d_u;
            tie(u, d_u) = p;
            
            if (d == dist[u] + d_u) {
                saved[p.first][v] = true;
                saved[v][p.first] = true;
                que.P(u);
            }
        }
    }

    pq.P(MP(u,0));

    vll dist2(n, INF);

    while(!pq.empty()){
        tie(distance, node) = pq.top();
        pq.pop();

        if(dist2[node] <= distance) continue;

        dist2[node] = distance;

        each(e, adj[node]){
            if(saved[e.first][node]){
                pq.P(MP(distance, e.first));
            }else{
                pq.P(MP(distance+e.second, e.first));
            }
        }
    }
    puts(dist2[v]);
}

int main() {
    // FAST;
    // READ_FILE("test.in", "test.out");
    ll t = 1;
    // cin >> t;

    loop(k,1,t+1,1) {
        // put("Case #", k, ": ");
        solve();
    }

    // cout << flush;
    return 0;
}

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