Submission #1026749

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026749		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	295 ms	25700 KiB

commuter_pass

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

class Q
{
    public:
        int node;
        long long cost;
    Q(int n, long long c): node(n), cost(c){}
    bool operator<(Q q) const
    {
        return cost>q.cost;
    }
};

set<int>dijkstra_1(int start, int end, vector<pair<int, long long int>>a[], int n)
{
    //vector<int>path;
    priority_queue<Q>q;
    set<int>path;
    long long dist[n], par[n];
    for(int i=0; i<n; i++)
    {
        dist[i]=LLONG_MAX;
        par[i]=-1;
    }
    q.push(Q(start, 0));
    dist[start]=0;
    while(!q.empty())
    {
        Q w=q.top();
        q.pop();
        if(dist[w.node]<w.cost)
            continue;
        dist[w.node]=w.cost;
        for(int i=0; i<a[w.node].size(); i++)
        {
            if(dist[a[w.node][i].first]>w.cost+a[w.node][i].second)
            {
                dist[a[w.node][i].first]=w.cost+a[w.node][i].second;
                q.push({a[w.node][i].first, dist[a[w.node][i].first]});
                par[a[w.node][i].first]=w.node;
            }
        }
    }
    for(int node=end; node!=start; node=par[node])
    {
        //path.push_back(node);
        path.insert(node);
    }
    path.insert(start);
    //path.push_back(start);
    //reverse(path.begin(), path.end());
    return path;
}
pair<long long, long long>dijkstra_2(int start, int end, vector<pair<int, long long int>>a[], int n, set<int>path)
{
    priority_queue<Q>q;
    long long dist[n];
    for(int i=0; i<n; i++)
    {
        dist[i]=LLONG_MAX;
    }
    dist[start]=0;
    q.push(Q(start, 0));
    long long dist1=LLONG_MAX;
    while(!q.empty())
    {
        Q w=q.top();
        q.pop();
        if(dist[w.node]<w.cost)
            continue;
        dist[w.node]=w.cost;
        if(path.find(w.node)!=path.end())
        {
            dist1=min(w.cost, dist1);
        }
        for(int i=0; i<a[w.node].size(); i++)
        {
            pair<int, long long>next=a[w.node][i];
            if(dist[next.first]>next.second+w.cost)
            {
                dist[next.first]=next.second+w.cost;
                q.push(Q(next.first, next.second+w.cost));
            }
        }
    }
    long long int dist2=dist[end];
    return {dist1, dist2};
}

int main()
{
    int n, m, S, T, U, V;
    cin>>n>>m>>S>>T>>U>>V;
    S--; T--; U--; V--;
    vector<pair<int, long long int>>a[n];
    for(int i=0; i<m; i++)
    {
        int aa, bb, cc;
        cin>>aa>>bb>>cc;
        aa--; bb--;
        a[aa].push_back({bb, cc});
        a[bb].push_back({aa, cc});
    }
    set<int>path=dijkstra_1(S, T, a, n);
    /*for(int i=0; i<path.size(); i++)
        cout<<path[i]<<" ";*/
    pair<long long, long long> dis1=dijkstra_2(U, V, a, n, path);
    pair<long long, long long> dis2=dijkstra_2(V, U, a, n, path);
    cout<<min(dis1.first+dis2.first, dis1.second);
    
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'std::set<int> dijkstra_1(int, int, std::vector<std::pair<int, long long int> >*, int)':
commuter_pass.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(int i=0; i<a[w.node].size(); i++)
      |                      ~^~~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'std::pair<long long int, long long int> dijkstra_2(int, int, std::vector<std::pair<int, long long int> >*, int, std::set<int>)':
commuter_pass.cpp:78:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         for(int i=0; i<a[w.node].size(); i++)
      |                      ~^~~~~~~~~~~~~~~~~

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