Submission #1086004

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086004		smile	Commuter Pass (JOI18_commuter_pass)	C++14	16 / 100	159 ms	22996 KiB

commuter_pass

#include <bits/stdc++.h>

#define smile "commuterpass."
#define mp make_pair
#define prior(type) priority_queue<type, vector<type>, greater<type> >

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using lli = pair<ll, int>;
// using iii = tuple<int, int, int>;

const int N = (int) 1e5 + 10;
const ll inf = (ll) 1e15;

int n, m;
int s1, t1;
int s2, t2;
vector<ii> g[N];

namespace SUB1 // s1 == s2
{
    vector<ll> d1, d2, d3;
    bitset<N> vis;
    void dijkstra(int s, vector<ll>& d)
    {
        d.assign(n+2, inf); vis.reset();
        prior(lli) q;
        q.push(mp(0LL, s));
        d[s] = 0;
        while (!q.empty())
        {
            int u = q.top().second;
            q.pop();
            if (vis[u]) continue;
            vis[u] = 1;
            for (ii t: g[u])
            {
                int v = t.second;
                if (!vis[v] && d[v] > d[u] + t.first)
                {
                    d[v] = d[u] + t.first;
                    q.push(mp(d[v], v));
                }
            }
        }
        
    }
    void solve()
    {
        dijkstra(s1, d1);
        dijkstra(t2, d2);
        dijkstra(t1, d3);
        ll ans = LLONG_MAX;
        for (int y = 1; y <= n; y++)
            if (d1[y] + d3[y] == d1[t1])
                ans = min(ans, d2[y]);
        cout << ans;
    }
}
namespace SUB3
{

    void solve()
    {

    }
}
namespace SUB2
{
    vector<ll> d;
    vector<int> trace;
    bitset<N> vis;
    set<int> free[N];
    void dijkstra(int s, int t)
    {
        d.assign(n+2, inf); trace.assign(n+2, 0); vis.reset();
        prior(lli) q;
        q.push(mp(0, s));
        d[s] = 0; trace[s] = -1;
        while (!q.empty())
        {
            int u = q.top().second;
            q.pop();
            if (u == t) return;
            if (vis[u]) continue;
            vis[u] = 1;
            for (ii x: g[u])
            {
                int v = x.second;
                if (!free[u].empty())
                {
                    if (free[u].find(v) != free[u].end())
                            x.first = 0;   
                }
                if (!vis[v] && d[v] > d[u] + x.first)
                {
                    d[v] = d[u] + x.first;
                    // if (v == 5 && s == 1) { cerr << d[v] << ' ';}

                    trace[v] = u;
                    q.push(mp(d[v], v));
                }
            }
        }
    }
    void solve()
    {
        dijkstra(s1, t1);   
        // cerr << s1 << ' ' << d[t1];
        for (int v = t1, u = trace[v]; v != s1 ; v = u, u = trace[v])
            free[u].insert(v); 
            // cerr << u << ' ' << v << '\n';
        // cerr << "\nok2";
        dijkstra(s2, t2);
        cout << d[t2];
    }
}
int main()
{
    //freopen(smile"inp", "r", stdin);
    //freopen(smile"out", "w", stdout);
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m;
    cin >> s1 >> t1;
    cin >> s2 >> t2;
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        // cout << a << ' ' << b << ' '<< c << '\n';
        g[a].push_back(mp(c, b));
        g[b].push_back(mp(c, a));
    }
    // SUB2::solve();
    if (s1 == s2)
        SUB1::solve();
    // else if (n <= 300)
    //     SUB3:: solve();
    else
        SUB2:: solve();
    return 0;
}

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