Submission #758650

#	Time	Username	Problem	Language	Result	Execution time	Memory
758650		kokoxuya	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	457 ms	30296 KiB

commuter_pass

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

//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)
{
    if (visited[start]) return 9223372036854775807;
    visited[start] = true;
    ans = distv[start];
    for (int x: usable_edges[start])
    {
        ans = min(ans,dp(x,visited,distv,ans,usable_edges));
    }
    cout << 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<int>>usable_edges(nodes + 1);
    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 ans, mind = distv[u];
    //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)
        { //if edge can be used
            usable_edges[temp1].push_back(temp2);
            usable_edges[temp2].push_back(temp1);
            ucount += 1;
        }
        else if (dists[temp2] + distt[temp1] + temp3 == mind)
        {
            usable_edges[temp2].push_back(temp1);
            usable_edges[temp1].push_back(temp2);
            ucount += 1;
        }
    }
    vector<bool> visited(nodes + 1);
    fill(visited.begin(),visited.end(),false);

    cout << dp(u,visited,distv,ans,usable_edges); 
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:114:48: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  114 |     cout << dp(u,visited,distv,ans,usable_edges);
      |                                                ^

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