Submission #679900

#	Time	Username	Problem	Language	Result	Execution time	Memory
679900		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	349 ms	26352 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define F first
#define S second
#define pb push_back
#define all(a) a.begin(), a.end()
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;

int n, m, s, t, u, v;
bool vis[N];
vector<ii> g[N];
ll dp[2][N], res;
ll ds[N], dv[N], du[N];

void dijkstra(int st, ll d[])
{
    for(int i = 0; i <= n; i++)
        vis[i] = 0, d[i] = 1e17;
        
    priority_queue<ii, vector<ii>, greater<ii>> q;
    q.emplace(0, st);
    d[st] = 0;
    while(q.size())
    {
        int u = q.top().S;
        int w = q.top().F;
        q.pop();
        if(w != d[u]) continue;
        for(ii &x : g[u])
        {
            ll wv = w + x.S;
            int v = x.F;
            if(wv < d[v])
            {
                d[v] = wv;
                q.emplace(wv, v);
            }
        }
    }
}

void dijkstra2(int st, int ed)
{
    for(int i = 0; i <= n; i++)
    {
        vis[i] = 0;
        dp[0][i] = dp[1][i] = 1e17;
        ds[i] = 1e17;
    }

    priority_queue<ii, vector<ii>, greater<ii>> q;
    q.emplace(0, st);
    ds[st] = 0;
    while(q.size())
    {
        int u = q.top().S;
        ll w = q.top().F;
        q.pop();
        
        if(w != ds[u]) continue;
        
        for(ii &x : g[u])
        {
            ll wv = w + x.S;
            int v = x.F;
            if(wv < ds[v])
            {
                ds[v] = wv;
                dp[0][v] = min(dp[0][u], du[v]);
                dp[1][v] = min(dp[1][u], dv[v]);
                q.emplace(w + x.S, v);
            }
            else if(wv == ds[v])
            {
                ll tmp1 = min(dp[0][u], du[v]);
                ll tmp2 = min(dp[1][u], dv[v]);
                
                if (tmp1 + tmp2 < dp[0][v] + dp[1][v])
                {
                    dp[0][v] = tmp1;
                    dp[1][v] = tmp2;
                }
            }
        }
    }
    res = min(res, dp[0][ed] + dp[1][ed]);
}

void solve()
{    
    cin >> n >> m >> s >> t >> u >> v;
    
    for(int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].pb(ii(v, w));
        g[v].pb(ii(u, w));
    }
    
    dijkstra(u, du);
    dijkstra(v, dv);
    res = du[v];
    dijkstra2(s, t);
    dijkstra2(t, s);
    cout << res;
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

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