Submission #497969

#	Time	Username	Problem	Language	Result	Execution time	Memory
497969		Karabasan	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	260 ms	25840 KiB

commuter_pass

#include <bits/stdc++.h>
#define ll long long
#define fast1 ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define int long long
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,avx")
#pragma GCC optimize("unroll-loops")

int n,m;
int dizi[100005];
int s,e;
int u,y;
vector<pair<int,int> > v[100005];
int st[100005];
int en[100005];
int vis[100005];
void solve()
{
    cin>>n>>m>>s>>e>>u>>y;
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        v[a].push_back({-c,b});
        v[b].push_back({-c,a});
    }
    priority_queue<pair<int,int> > pq;
    pq.push({0,e});
    while(!pq.empty())
    {
        int x=pq.top().second;
        int yol=pq.top().first;
        pq.pop();
        if(vis[x])
            continue;
        vis[x]=1;
        en[x]=yol;
        for(int i=0;i<v[x].size();i++)
        {
            if(!vis[v[x][i].second])
                pq.push({yol+v[x][i].first,v[x][i].second});
        }
    }
    memset(vis,0,sizeof vis);
    while(!pq.empty())
        pq.pop();
    pq.push({0,s});
    while(!pq.empty())
    {
        int x=pq.top().second;
        int yol=pq.top().first;
        pq.pop();
        if(vis[x])
            continue;
        vis[x]=1;
        st[x]=yol;
        for(int i=0;i<v[x].size();i++)
        {
            if(!vis[v[x][i].second])
                pq.push({yol+v[x][i].first,v[x][i].second});
        }
    }
    memset(vis,0,sizeof vis);
    priority_queue<pair<int,pair<int,int> > >q;
    if(st[u]+en[u]!=st[e])
        q.push({0,{u,0}});
    else q.push({0,{u,1}});
    while(!q.empty())
    {
        int x=q.top().second.first;
        int yol=q.top().first;
        int ktr=q.top().second.second;
        q.pop();
        if(vis[x])
            continue;
        vis[x]=1;
        if(x==y)
        {
            cout<<-yol<<endl;
            return;
        }
        for(int i=0;i<v[x].size();i++)
        {
            if(!vis[v[x][i].second])
            {
                //cout<<v[x][i].second<<" "<<st[x]<<" "<<en[x]<<endl;
                if(ktr==2)
                    q.push({yol+v[x][i].first,{v[x][i].second,2}});
                else if((st[v[x][i].second]+en[v[x][i].second]!=st[e]||st[x]+en[x]!=st[e])&&ktr==0)
                    q.push({yol+v[x][i].first,{v[x][i].second,0}});
                else if((st[v[x][i].second]+en[v[x][i].second]!=st[e]||st[x]+en[x]!=st[e])&&ktr==1)
                    q.push({yol+v[x][i].first,{v[x][i].second,2}});
                else
                    q.push({yol,{v[x][i].second,1}});
            }
        }
    }
}
signed main()
{
    fast1
    //freopen ("lca.gir","r",stdin);
    //freopen ("lca.cik","w",stdout);
    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:40: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]
   40 |         for(int i=0;i<v[x].size();i++)
      |                     ~^~~~~~~~~~~~
commuter_pass.cpp:59: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]
   59 |         for(int i=0;i<v[x].size();i++)
      |                     ~^~~~~~~~~~~~
commuter_pass.cpp:84: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]
   84 |         for(int i=0;i<v[x].size();i++)
      |                     ~^~~~~~~~~~~~

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