Submission #654504

#	Time	Username	Problem	Language	Result	Execution time	Memory
654504		hail	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	378 ms	25196 KiB

commuter_pass

#include <bits/stdc++.h>
 
using namespace std;
 
#define vi vector<int>
#define vll vector<long long>
#define pb push_back
using ll= long long;
#define fast_io ios::sync_with_stdio(0); cin.tie(0)
#define inpint(x) int x; cin>>x
#define inpll(x) long long x; cin>>x
#define fl(i, n) for(int i=0; i<n; i++)
#define flo(i, n) for(int i=1; i<=n; i++)
#define int long long 
#define pi pair<int, int>
#define mp make_pair
#define ld long double

const int MOD = 7 + (int)1e9;
const int INF = (int)1e18;

//

void solve()
{
    int n, m;
    cin>>n>>m;
    int s, t;
    cin>>s>>t;
    int u, v;
    cin>>u>>v;

    vector<vector<pi>> adjlist(n+1, vector<pi>(0));

    for(int i=1; i<=m; i++)
    {
        int a, b, c;
        cin>>a>>b>>c;

        adjlist[a].pb({b, c});
        adjlist[b].pb({a, c});
    }

    vector<int> vc(n+1, INF);
    vector<int> uc(n+1, INF);

    priority_queue<pi, vector<pi>, greater<pi>> pq;
    uc[u] = 0;
    vc[v] = 0;
    pq.push({0, u});
    while(not pq.empty())
    {
        int i = pq.top().second;
        int c = pq.top().first;

        pq.pop();

        if(uc[i]<c) continue;

        for(auto j: adjlist[i])
        {
            if(uc[j.first]<=c+j.second) continue;
            uc[j.first] = c+j.second;
            pq.push({uc[j.first], j.first});
        }
    }

    pq.push({0, v});
    while(not pq.empty())
    {
        int i = pq.top().second;
        int c = pq.top().first;

        pq.pop();

        if(vc[i]<c) continue;

        for(auto j: adjlist[i])
        {
            if(vc[j.first]<=c+j.second) continue;
            vc[j.first] = c+j.second;
            pq.push({vc[j.first], j.first});
        }
    }

    int ans = uc[v];


    vector<int> minsu(n+1, INF);
    vector<int> mintu(n+1, INF);
    vector<int> minsv(n+1, INF);
    vector<int> mintv(n+1, INF);
    vector<int> sc(n+1, INF);
    vector<int> tc(n+1, INF);

    sc[s] = 0;
    tc[t] = 0;
    minsu[s] = uc[s];
    minsv[s] = vc[s];
    mintu[t] = uc[t];
    mintv[t] = vc[t];

    pq.push({0, s});

    while(not pq.empty())
    {
        int i = pq.top().second;
        int c = pq.top().first;

        pq.pop();

        if(c>sc[i]) continue;

        for(auto j: adjlist[i])
        {
            int cd = c + j.second;
            if(cd==sc[j.first])
            {
                minsu[j.first] = min(minsu[i], minsu[j.first]);
                minsv[j.first] = min(minsv[i], minsv[j.first]);
                continue;
            }
            if(cd>sc[j.first]) continue;
            minsu[j.first] = min(minsu[i], uc[j.first]);
            minsv[j.first] = min(minsv[i], vc[j.first]);
            sc[j.first] = cd;
            pq.push({sc[j.first], j.first});
        }
    }

    int st = sc[t];

    pq.push({0, t});

    vector<bool> visited(n+1, false);

    while(not pq.empty())
    {
        int i = pq.top().second;
        int c = pq.top().first;
        visited[i] = true;

        pq.pop();

        if(c>tc[i]) continue;

        for(auto j: adjlist[i])
        {
            int cd = c + j.second;
            if(visited[j.first])
            {
                int x = sc[i] + tc[j.first] + j.second;
                int y = sc[j.first] + tc[i] + j.second;
                if(x==st || y==st)
                {
                    if(sc[i]<sc[j.first])
                    {
                        x = minsu[i] + mintv[j.first];
                        y = minsv[i] + mintu[j.first];
                        ans = min({ans, x, y});
                        continue;
                    }
                    else
                    {
                        x = mintu[i] + minsv[j.first];
                        y = mintv[i] + minsu[j.first];
                        ans = min({ans, x, y});
                        continue;
                    }
                }
            }
            if(cd==tc[j.first])
            {
                mintu[j.first] = min(mintu[i], mintu[j.first]);
                mintv[j.first] = min(mintv[i], mintv[j.first]);
                continue;
            }
            if(cd>tc[j.first]) continue;
            mintu[j.first] = min(mintu[i], uc[j.first]);
            mintv[j.first] = min(mintv[i], vc[j.first]);
            tc[j.first] = cd;
            pq.push({tc[j.first], j.first});
        }
    }  

    cout<<ans;  
}

signed main()
{
    fast_io;

    int t=1; 
    //cin>>t;
    while(t--)
    {
        solve();
    }
    cout<<endl;
}

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