Submission #833320

#	Time	Username	Problem	Language	Result	Execution time	Memory
833320		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	210 ms	25464 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
const ll MX = 1e5 + 5, INF = 1e18;

vector<pair<ll,ll>> adj[MX];
vector<array<int,3>> edges(2*MX);
vector<ll> distS(MX, INF);
vector<ll> distT(MX, INF);
vector<ll> dist(MX, INF);
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,m;
    cin >> n >> m;
    
    ll s,t,u,v;
    cin >> s >> t >> u >> v;

    for(int a,b,c,i = 1 ; i <= m ; i++)
    {
        cin >> a >> b >> c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
        edges[i] = {a,b,c};
    }

    priority_queue<pii,vector<pii>, greater<pii>> pq;
    distS[s] = 0;
    pq.push({0,s});

    while(!pq.empty()){
        ll cost = pq.top().first, V = pq.top().second;
        pq.pop();
        if(distS[V] != cost){
            continue;
        }
        for(auto U : adj[V])
        {
            ll nxt = U.first, w = U.second;
            
            if(distS[nxt] > cost + w)
            {
                distS[nxt] = cost + w;
                pq.push({distS[nxt],nxt});
            }
        }
    }
    ll sp = distS[t];
    distT[t] = 0;

    pq.push({0,t});

    while(!pq.empty()){
        ll cost = pq.top().first, V = pq.top().second;
        pq.pop();
        if(distT[V] != cost){
            continue;
        }
        for(auto U : adj[V])
        {
            ll nxt = U.first, w = U.second;
            
            if(distT[nxt] > cost + w)
            {
                distT[nxt] = cost + w;
                pq.push({distT[nxt],nxt});
            }
        }
    }

    for(int i = 1 ; i<= m ; i++){

        ll a,b,c;
        a = edges[i][0], b =edges[i][1], c = edges[i][2];
        if((distS[a] + distT[b]  + c == sp )||(distS[b] + distT[a] + c == sp) ){
            //cout <<" y";
            adj[a].push_back({b,0});
            adj[b].push_back({a,0});
        }
    }

    dist[u] = 0;
    pq.push({0,u});
    while(!pq.empty()){
        ll cost = pq.top().first, V = pq.top().second;
        pq.pop();
        if(dist[V] != cost){
            continue;
        }   
        for(auto U : adj[V])
        {
            ll nxt = U.first, w = U.second;
            
            if(dist[nxt] > cost + w)
            {
                dist[nxt] = cost + w;
                pq.push({dist[nxt],nxt});
            }
        }
    }

    cout << dist[v];


    return 0;
}

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