Submission #1026809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026809		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	2049 ms	262144 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;
    }
};

void dfs(int node, int start, vector<set<int>>&paths, set<int>path, vector<int>par[])
{
    path.insert(node);
    if(start==node)
    {
        paths.push_back(path);
    }
    else
    {
        for(int i=0; i<par[node].size(); i++)
        {
            dfs(par[node][i], start, paths, path, par);
        }
    }
    path.erase(node);
}

vector<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];
    vector<int>par[n];
    for(int i=0; i<n; i++)
    {
        dist[i]=LLONG_MAX;
    }
    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].clear();
                par[a[w.node][i].first].push_back(w.node);
            }
            else if(dist[a[w.node][i].first]==w.cost+a[w.node][i].second)
                par[a[w.node][i].first].push_back(w.node);
        }
    }
    vector<set<int>>paths;
    dfs(end, start, paths, path, par);
    for(int i=0; i<n; i++)
        par[i].clear();
    /*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 paths;
}
pair<long long, long long>dijkstra_2(int start, int end, vector<pair<int, long long int>>a[], int n, vector<set<int>>paths)
{
    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;
        for(int i=0; i<paths.size(); i++)
        {
            if(paths[i].find(w.node)!=paths[i].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});
    }
    vector<set<int>>paths=dijkstra_1(S, T, a, n);
    /*cout<<paths.size();
    for(int i=0; i<paths.size(); i++)
    {
        for(auto it=paths[i].begin(); it!=paths[i].end(); it++)
        {
            cout<<*it<<" ";
        }
        cout<<endl;
    }
    cout<<endl;*/
    pair<long long, long long> dis1=dijkstra_2(U, V, a, n, paths);
    pair<long long, long long> dis2=dijkstra_2(V, U, a, n, paths);
    cout<<min(dis1.first+dis2.first, dis1.second);
    
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dfs(int, int, std::vector<std::set<int> >&, std::set<int>, std::vector<int>*)':
commuter_pass.cpp:25:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for(int i=0; i<par[node].size(); i++)
      |                      ~^~~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'std::vector<std::set<int> > dijkstra_1(int, int, std::vector<std::pair<int, long long int> >*, int)':
commuter_pass.cpp:53: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]
   53 |         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::vector<std::set<int> >)':
commuter_pass.cpp:98:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::set<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         for(int i=0; i<paths.size(); i++)
      |                      ~^~~~~~~~~~~~~
commuter_pass.cpp:105: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]
  105 |         for(int i=0; i<a[w.node].size(); i++)
      |                      ~^~~~~~~~~~~~~~~~~

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