Submission #565318

#	Time	Username	Problem	Language	Result	Execution time	Memory
565318		groshi	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	517 ms	40996 KiB

commuter_pass

#include<iostream>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>
using namespace std;
long long inf=1e18;
#define int long long
#define tak int
struct wi{
    vector<pair<int,int> > Q,przed,po;
    long long odl[4]={inf,inf,inf,inf};
    int przed_size=0;
    long long dp1=1e18,dp2=1e18;
}*w;
int t[1000000][3];
void dijkstra(int skad,int gdzie)
{
    priority_queue<pair<int,int> > kolejka;
    kolejka.push({0,skad});
    while(!kolejka.empty())
    {
        pair<int,int> para=kolejka.top();
        kolejka.pop();
        if(w[para.second].odl[gdzie]!=1e18)
            continue;
        //cout<<para.second<<" "<<gdzie<<" "<<-para.first<<"\n";
        w[para.second].odl[gdzie]=-para.first;
        for(int i=0;i<w[para.second].Q.size();i++)
        {
            int kto=w[para.second].Q[i].first;
            int ile=w[para.second].Q[i].second;
            if(w[kto].odl[gdzie]!=1e18)
                continue;
            kolejka.push({para.first-ile,kto});
        }
    }
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,s,tt,u,v,x,y,z;
    cin>>n>>m>>s>>tt>>u>>v;
    w=new wi[n+3];
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>z;
        w[x].Q.push_back({y,z});
        w[y].Q.push_back({x,z});
        t[i][0]=x;
        t[i][1]=y;
        t[i][2]=z;
    }
    dijkstra(s,0);
    dijkstra(u,1);
    dijkstra(v,2);
    dijkstra(tt,3);
    long long odl_s=w[tt].odl[0];
    //cout<<" "<<odl_s<<"\n";
    for(int i=1;i<=m;i++)
    {
        //cout<<w[t[i][0]].odl[0]<<" "<<w[t[i][1]].odl[0]<<" "<<i<<"\n";
        if(w[t[i][0]].odl[0]==w[t[i][1]].odl[0]+t[i][2] && w[t[i][0]].odl[0]+w[t[i][0]].odl[3]==odl_s && w[t[i][1]].odl[0]+w[t[i][1]].odl[3]==odl_s)
        {
            w[t[i][0]].przed.push_back({t[i][1],t[i][2]});
            w[t[i][1]].po.push_back({t[i][0],t[i][2]});
        }
        //cout<<w[t[i][0]].odl[3]<<" "<<w[t[i][1]].odl[3]<<"\n";
        if(w[t[i][1]].odl[0]==w[t[i][0]].odl[0]+t[i][2] && w[t[i][0]].odl[0]+w[t[i][0]].odl[3]==odl_s && w[t[i][1]].odl[0]+w[t[i][1]].odl[3]==odl_s)
        {
            w[t[i][1]].przed.push_back({t[i][0],t[i][2]});
            w[t[i][0]].po.push_back({t[i][1],t[i][2]});
        }
    }
    for(int i=1;i<=n;i++)
        w[i].przed_size=w[i].przed.size();
    long long wynik=w[u].odl[2];
    //cout<<wynik<<"\n";
    queue<int> kolejka;
    kolejka.push(s);
    while(!kolejka.empty())
    {
        int x=kolejka.front();
        kolejka.pop();
        //cout<<x<<"\n";
        for(int i=0;i<w[x].przed.size();i++)
        {
            int kto=w[x].przed[i].first;
            w[x].dp1=min({w[x].dp1,w[kto].dp1,w[kto].odl[1]});
            w[x].dp2=min({w[x].dp2,w[kto].dp2,w[kto].odl[2]});
        }
        //cout<<w[x].po.size()<<"\n";
        wynik=min({wynik,w[x].dp1+w[x].odl[2],w[x].dp2+w[x].odl[1]});
        for(int i=0;i<w[x].po.size();i++)
        {
            int kto=w[x].po[i].first;
            w[kto].przed_size--;
            if(w[kto].przed_size==0)
                kolejka.push(kto);
        }
    }
    cout<<wynik;
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(long long int, long long int)':
commuter_pass.cpp:29:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for(int i=0;i<w[para.second].Q.size();i++)
      |                     ~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'int32_t main()':
commuter_pass.cpp:88:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         for(int i=0;i<w[x].przed.size();i++)
      |                     ~^~~~~~~~~~~~~~~~~~
commuter_pass.cpp:96:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         for(int i=0;i<w[x].po.size();i++)
      |                     ~^~~~~~~~~~~~~~~

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