Submission #759273

#	Time	Username	Problem	Language	Result	Execution time	Memory
759273		kokoxuya	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	539 ms	37152 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long lo;
#define llmax 9223372036854775807

//note: everything is one-indexed
lo nodes, edges, s,t,u,v, temp1,temp2,temp3;
vector<tuple<lo,lo,lo>>elist(200001);
vector<vector<pair<lo,lo>>>adjlist(100001);

int ucount = 0;
//ducks 
lo dp(lo start, vector<bool> &visited, vector<lo> &distv, lo ans, vector<vector<int>> &usable_edges, vector<lo> &minnow)
{
    if (visited[start])
    {
        //cout << "once, " << start << " " << visited[start];
        return minnow[start];
    }
    visited[start] = true;
    ans = distv[start];
    //cout << ans;
    for (int x: usable_edges[start])
    {
        //cout << start << " connects to " << x << " \n";
        ans = min(ans,dp(x,visited,distv,ans,usable_edges,minnow));
    }
    //cout << "For starting node " << start << " : ";
    //cout << ans << "\n";
    minnow[start] = ans;
    return ans;
}


void dijkstra(int n, vector<lo> &dist)
{
    priority_queue<pair<lo,lo>, vector<pair<lo,lo>> , greater<pair<lo,lo>>>pq;
    fill(dist.begin(),dist.end(),-1);
    lo temp1,temp2,temp3,temp4;
    pq.push(make_pair(0,n));
    //cout << "pq: " << pq.top().first << " " << pq.top().second << "\n";


    while (!pq.empty())
    {
        tie(temp1,temp2) = pq.top(); // cost, node
        pq.pop();
        if (dist[temp2] != -1) //already visited
        {
            continue;
        }
        dist[temp2] = temp1;
        //cout << "Initialising " << temp2 << " to " << temp1 << "\n";
        for (auto x : adjlist[temp2])
        {
            tie(temp3,temp4) = x; //cost, node
            pq.push(make_pair(temp1 + temp3, temp4));
        }
    }
}




int main()
{
    cin >> nodes >> edges >> s >> t >> u >> v;
    //cout << "v: " << v << "\n";
    vector<vector<vector<int>>>usable_edges(2, vector<vector<int>>(nodes + 1)); //direction used, diff direction
    for (int a = 1; a <= edges; a++)
    {
        cin >> temp1 >> temp2 >> temp3;
        adjlist[temp1].push_back(make_pair(temp3,temp2));
        adjlist[temp2].push_back(make_pair(temp3,temp1));
        elist[a] = make_tuple(temp1,temp2,temp3);
    }
    /*cout << "Outputting all edges: (cost,start,end)\n";
    for (int a = 1; a <= nodes; a++)
    {
        for (auto x: adjlist[a])
        {
            int b,c;
            tie(b,c) = x;
            cout << b << " " << a << " " << c << "\n";
        }
    }*/

    vector<lo>dists(nodes + 1),distu(nodes + 1),distt(nodes + 1),distv(nodes + 1);
    dijkstra(s,dists);dijkstra(t,distt);dijkstra(u,distu);dijkstra(v,distv);
    /*cout << "Outputting minimum distances from s: \n";
    for (int a = 1; a <= nodes; a++)
    { 
        cout << dists[a] << " ";
    }
    cout << " \nOutputting minimum distance from u ;)\n";
    for (int a = 1; a <= nodes; a++)
    { 
        cout << distu[a] << " ";
    }
    cout << " \n";*/
    lo  mind = distt[s];
    //cout << "ans and mind: " << ans << " " << mind << "\n";

    for (int a = 1; a <= edges; a++) //for each edge
    {
        tie(temp1,temp2,temp3) = elist[a]; //start,end,cost
        if (dists[temp1] + distt[temp2] + temp3 == mind) //temp1 to temp2
        { //if edge can be used
            usable_edges[0][temp1].push_back(temp2); 
            usable_edges[1][temp2].push_back(temp1);
            ucount += 1;
        }
        else if (dists[temp2] + distt[temp1] + temp3 == mind)
        {
            usable_edges[0][temp2].push_back(temp1);
            usable_edges[1][temp1].push_back(temp2);
            ucount += 1;
        }
    }
    /*for (int a = 1; a <= nodes; a++)
    {
        cout << a << " : ";
        for (int b : usable_edges[a])
        {
            cout << b << " ";
        }
        cout << "\n";
    }*/
    /*cout << "distance from v \n\n";
    for (int a = 1; a <= nodes; a++)
    {
        cout << "From node " << a << " : " << distv[a] << "\n"; 
    }
    cout << "distance from u ;)\n";
    for (int a = 1; a <= nodes; a++)
    {
        cout << "From node " << a << " : " << distu[a] << "\n"; 
    }*/
    /*cout << "Outputting usable_edges: \n";
    for (int a = 0; a < nodes; a++)
    {
        cout << a << " : ";
        for (int x : usable_edges[1][a])
        {
            cout << x << " ";
        }
        cout << "\n";
    }
    for (int a = 0; a < nodes; a++)
    {
        cout << a << " : ";
        for (int x : usable_edges[0][a])
        {
            cout << x << " ";
        }
        cout << "\n";
    }*/
    vector<bool> visited(nodes + 1);
    vector<lo>minnow(nodes + 1);
    fill(minnow.begin(),minnow.end(),-1);
    long long ans = distv[u];
    for (int b = 0; b < 2; b++)
    {    
        fill(minnow.begin(),minnow.end(),-1);    
        fill(visited.begin(),visited.end(),false);    
        for (int a = 1; a <=nodes; a++)
        {
            //cout << a << " ";
            ans = min(ans,distu[a] + dp(a,visited,distv,ans,usable_edges[b],minnow));
        }
    }

    //cout << "Outputting: \n";
    cout << ans;
}

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