Submission #268253

#	Time	Username	Problem	Language	Result	Execution time	Memory
268253		MKopchev	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	719 ms	24412 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
const int nmax=1e5+42;

int n,m;

vector< pair<int/*to*/,int/*cost*/> > adj[nmax];

int s,t;

int u,v;

long long dist[4][nmax];//from s, from t, from u, from v

priority_queue< pair<long long/*dist*/,int/*node*/> > pq;

void dij(int node,int id)
{
    pq.push({0,node});

    while(pq.size())
    {
        pair<long long/*dist*/,int/*node*/> tp=pq.top();
        pq.pop();

        tp.first=-tp.first;

        //cout<<tp.first<<" "<<tp.second<<endl;

        if(dist[id][tp.second]!=-1)continue;

        dist[id][tp.second]=tp.first;

        for(auto k:adj[tp.second])
        {
            pq.push({-(tp.first+k.second),k.first});
            //cout<<"edge "<<k.first<<" "<<k.second<<endl;
        }
    }
    /*
    cout<<id<<endl;
    for(int i=1;i<=n;i++)cout<<dist[id][i]<<" ";cout<<endl;
    */
}

long long mini[nmax];
bool been[nmax];

vector<int> dag_edges[nmax];

int OTHER;

long long find_mini(int node)
{
    if(been[node])return mini[node];

    mini[node]=dist[OTHER][node];

    for(auto k:dag_edges[node])
    {
        mini[node]=min(mini[node],find_mini(k));
    }

    been[node]=1;
    return mini[node];
}

long long solve(int original,int other)
{
    //cout<<original<<" "<<other<<" : "<<endl;

    OTHER=other;

    memset(been,0,sizeof(been));
    for(int i=1;i<=n;i++)mini[i]=1e18;

    for(int i=1;i<=n;i++)dag_edges[i]={};
    for(int i=1;i<=n;i++)
        for(auto k:adj[i])
            if(dist[0][i]+k.second+dist[1][k.first]==dist[0][t]&&dist[0][i]<dist[0][k.first])
            {
                //cout<<i<<" -> "<<k.first<<endl;
                dag_edges[i].push_back(k.first);
            }
    /*
    cout<<"find mini"<<endl;
    for(int i=1;i<=n;i++)cout<<i<<" -> "<<find_mini(i)<<endl;
    */
    long long ret=1e18;

    for(int i=1;i<=n;i++)
    {
        long long cur=dist[original][i];
        cur=cur+find_mini(i);

        //cout<<i<<" -> "<<cur<<" "<<dist[original][i]<<" "<<find_mini(i)<<endl;

        ret=min(ret,cur);
    }

    //cout<<"ret= "<<ret<<endl;
    return ret;
}
int main()
{
    memset(dist,-1,sizeof(dist));

    scanf("%i%i",&n,&m);

    scanf("%i%i",&s,&t);

    scanf("%i%i",&u,&v);

    for(int i=1;i<=m;i++)
    {
        int a,b,c;

        scanf("%i%i%i",&a,&b,&c);

        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }

    dij(s,0);
    dij(t,1);
    dij(u,2);
    dij(v,3);

    long long outp=dist[3][u];

    outp=min(outp,solve(3,2));

    outp=min(outp,solve(2,3));

    printf("%lld\n",outp);
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:108:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  108 |     scanf("%i%i",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
commuter_pass.cpp:110:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  110 |     scanf("%i%i",&s,&t);
      |     ~~~~~^~~~~~~~~~~~~~
commuter_pass.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  112 |     scanf("%i%i",&u,&v);
      |     ~~~~~^~~~~~~~~~~~~~
commuter_pass.cpp:118:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  118 |         scanf("%i%i%i",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

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