Submission #492863

#	Time	Username	Problem	Language	Result	Execution time	Memory
492863		Karabasan	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	254 ms	29044 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,a,b,u,cvp;
vector<pair<int,pair<int,int> > > v[100005];
int vis[100005];
pair<int,int> ata[100005];
int mark[200005];
void bul(int x)
{
    if(x==a)
        return;
    mark[ata[x].second]=1;
    bul(ata[x].first);
}
void solve()
{
    cin>>n>>m;
    cin>>a>>b;
    cin>>u>>cvp;
    for(int i=1;i<=m;i++)
    {
        int uy,yu,yol;
        cin>>yu>>uy>>yol;
        v[uy].push_back({-yol,{yu,i}});
        v[yu].push_back({-yol,{uy,i}});
    }
    priority_queue<pair<int,int>  > pq;
    pq.push({0,a});
    while(!pq.empty())
    {
        int x=pq.top().second;
        int yol=pq.top().first;
        pq.pop();
        if(vis[x])
            continue;
        vis[x]=1;
        if(x==b)
            break;
        for(int i=0;i<v[x].size();i++)
        {
            if(vis[v[x][i].second.first]==1)
                continue;
            pq.push({yol+v[x][i].first,v[x][i].second.first});
            ata[v[x][i].second.first]={x,v[x][i].second.second};
        }
    }
    bul(b);
    priority_queue<pair<int,int> > pq1;
    pq1.push({0,u});
    memset(vis,0,sizeof vis);
    while(!pq1.empty())
    {
        int x=pq1.top().second;
        int yol=pq1.top().first;
        pq1.pop();
        if(vis[x])
            continue;
        vis[x]=1;
        if(x==cvp)
        {
            cout<<-yol<<endl;
            return;
        }
        for(int i=0;i<v[x].size();i++)
        {
            if(vis[v[x][i].second.first]==1)
                continue;
            if(mark[v[x][i].second.second])
                pq1.push({yol,v[x][i].second.first});
            else pq1.push({yol+v[x][i].first,v[x][i].second.first});
        }
    }
}
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:47:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for(int i=0;i<v[x].size();i++)
      |                     ~^~~~~~~~~~~~
commuter_pass.cpp:72:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for(int i=0;i<v[x].size();i++)
      |                     ~^~~~~~~~~~~~

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