제출 #499039

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
499039		Karabasan	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	329 ms	25404 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<pair<int,int>,pair<int,int> > >q;
    if(st[u]+en[u]!=st[e])
        q.push({{0,0},{u,0}});
    else q.push({{0,0},{u,1}});
    while(!q.empty())
    {
        int x=q.top().second.first;
        int yol=q.top().first.first;
        int ktr=q.top().second.second;
        int ata=q.top().first.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[v[x][i].second]<<" "<<st[x]<<" "<<st[ata]<<endl;
                if((st[v[x][i].second]>=st[x]&&st[ata]>=st[x]||st[v[x][i].second]<=st[x]&&st[ata]<=st[x])&&ktr==2&&ata!=0)
                    q.push({{yol+v[x][i].first,x},{v[x][i].second,2}});
                else if((st[v[x][i].second]>=st[x]&&st[ata]>=st[x]||st[v[x][i].second]<=st[x]&&st[ata]<=st[x])&&ktr==1&&ata!=0)
                    q.push({{yol+v[x][i].first,x},{v[x][i].second,2}});
                else if((st[v[x][i].second]>=st[x]&&st[ata]>=st[x]||st[v[x][i].second]<=st[x]&&st[ata]<=st[x])&&ktr==0&&ata!=0)
                    q.push({{yol+v[x][i].first,x},{v[x][i].second,0}});
                else if(ktr==2)
                    q.push({{yol+v[x][i].first,x},{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,x},{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,x},{v[x][i].second,2}});
                else
                    q.push({{yol,x},{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;
}

컴파일 시 표준 에러 (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:85: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]
   85 |         for(int i=0;i<v[x].size();i++)
      |                     ~^~~~~~~~~~~~
commuter_pass.cpp:90:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   90 |                 if((st[v[x][i].second]>=st[x]&&st[ata]>=st[x]||st[v[x][i].second]<=st[x]&&st[ata]<=st[x])&&ktr==2&&ata!=0)
      |                     ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:92:51: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   92 |                 else if((st[v[x][i].second]>=st[x]&&st[ata]>=st[x]||st[v[x][i].second]<=st[x]&&st[ata]<=st[x])&&ktr==1&&ata!=0)
      |                          ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:94:51: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   94 |                 else if((st[v[x][i].second]>=st[x]&&st[ata]>=st[x]||st[v[x][i].second]<=st[x]&&st[ata]<=st[x])&&ktr==0&&ata!=0)
      |                          ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

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