Submission #851685

#	Time	Username	Problem	Language	Result	Execution time	Memory
851685		lftroq	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	213 ms	262144 KiB

commuter_pass

/*
                     ,
                ,.  | \
               |: \ ; :\
               :' ;\| ::\
                \ : | `::\
                _)  |   `:`.
              ,' , `.    ;: ;
            ,' ;:  ;"'  ,:: |_
           /,   ` .    ;::: |:`-.__
        _,' _o\  ,::.`:' ;  ;   . '
    _,-'           `:.          ;""\,
 ,-'                     ,:         `-;,
 \,                       ;:           ;--._
  `.______,-,----._     ,' ;:        ,/ ,  ,`
         / /,-';'  \     ; `:      ,'/,::.:::
       ,',;-'-'_,--;    ;   :.   ,',',;::::::
      ( /___,-'     `.     ;::,,'o/  ,:::::::
       `'             )    ;:,'o /  ;"-   -::
                      \__ _,'o ,'         ,::
                         ) `--'       ,..::::
      _lftroq_           ; `.        ,:::::::
                          ;  ``::.    :::::::
*/
#include <bits/stdc++.h>
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MOD 1000000007LL
#define MOD2 998244353LL
#define endl '\n'
#define INFINITE 2147483647LL
#define INFINITE2 9223372036854775807
#define llll pair<ll,ll>
#define ldld pair<ld,ld>
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using namespace std;

ll n,m,s,t,x,y;
vector<llll> graph[100005],rraph[100005];
vector<ll> trace[100005];
ll u[100005],v[100005],w[100005],d[100005],d1[100005],dlast[100005];

void dijkstra(ll s)
{
    memset(d,0x3f,sizeof(d));
    d[s]=0;
    priority_queue<llll,vector<llll>,greater<llll>> pq;
    pq.push({d[s],s});
    while(pq.size())
    {
        ll u=pq.top().se;
        pq.pop();
        for(int i=0;i<graph[u].size();i++)
        {
            ll v=graph[u][i].fi,w=graph[u][i].se;
            if(d[v]>d[u]+w)
            {
                d[v]=d[u]+w;
                pq.push({d[v],v});
            }
        }
    }
}

void dijkstra1(ll s)
{
    memset(d1,0x3f,sizeof(d1));
    d1[s]=0;
    priority_queue<llll,vector<llll>,greater<llll>> pq;
    pq.push({d1[s],s});
    while(pq.size())
    {
        ll u=pq.top().se;
        pq.pop();
        for(int i=0;i<graph[u].size();i++)
        {
            ll v=graph[u][i].fi,w=graph[u][i].se;
            if(d1[v]>d1[u]+w)
            {
                d1[v]=d1[u]+w;
                pq.push({d1[v],v});
            }
        }
    }
}

void solve1()
{
    dijkstra(s);
    dijkstra1(t);
    vector<bool> check(100005);
    for(int i=1;i<=m;i++)
    {
        if(d[u[i]]+d1[v[i]]+w[i]==d[t]) check[u[i]]=check[v[i]]=true;
        if(d[v[i]]+d1[u[i]]+w[i]==d[t]) check[u[i]]=check[v[i]]=true;
    }
    ll ans=INFINITE2;
    dijkstra(y);
    for(int i=1;i<=n;i++) if(check[i]) ans=min(ans,d[i]);
    cout << ans << endl;
}

void dijkstratrace(ll s)
{
    memset(d,0x3f,sizeof(d));
    d[s]=0;
    trace[s]={1};
    priority_queue<llll,vector<llll>,greater<llll>> pq;
    pq.push({d1[s],s});
    while(pq.size())
    {
        ll u=pq.top().se;
        pq.pop();
        vector<ll> temp=trace[u];
        for(int i=0;i<rraph[u].size();i++)
        {
            ll v=rraph[u][i].fi,w=rraph[u][i].se;
            if(d[v]>d[u]+w)
            {
                d[v]=d[u]+w;
                pq.push({d[v],v});
                for(int i=0;i<trace[u].size();i++) trace[v].push_back(trace[u][i]++);
            }
            else if(d[v]==d[u]+w) for(int i=0;i<trace[u].size();i++) trace[v].push_back(trace[u][i]++);
        }
        trace[u]=temp;
    }
}

void dijkstralast(ll s,ll k)
{
    memset(dlast,0x3f,sizeof(dlast));
    dlast[s]=0;
    priority_queue<llll,vector<llll>,greater<llll>> pq;
    pq.push({dlast[s],s});
    while(pq.size())
    {
        ll u=pq.top().se;
        pq.pop();
        for(int i=0;i<graph[u].size();i++)
        {
            ll v=graph[u][i].fi,w=graph[u][i].se;
            if(trace[u].size()&&trace[u].back()>=k&&trace[v].size()&&trace[v].back()>=k)
            {
                if(*lower_bound(trace[u].begin(),trace[u].end(),k)==k&&*lower_bound(trace[v].begin(),trace[v].end(),k)==k) w=0;
            }
            if(dlast[v]>dlast[u]+w)
            {
                dlast[v]=dlast[u]+w;
                pq.push({dlast[v],v});
            }
        }
    }
}

void solve()
{
    cin >> n >> m >> s >> t >> x >> y;
    for(int i=1;i<=m;i++)
    {
        cin >> u[i] >> v[i] >> w[i];
        graph[u[i]].push_back({v[i],w[i]});
        graph[v[i]].push_back({u[i],w[i]});
    }
    if(s==x)
    {
        solve1();
        return;
    }
    if(s==y)
    {
        swap(x,y);
        solve1();
        return;
    }
    dijkstra(s);
    dijkstra1(t);
    for(int i=1;i<=m;i++)
    {
        if(d[u[i]]+d1[v[i]]+w[i]==d[t])
        {
            rraph[u[i]].push_back({v[i],w[i]});
            rraph[v[i]].push_back({u[i],w[i]});
        }
        if(d[v[i]]+d1[u[i]]+w[i]==d[t])
        {
            rraph[u[i]].push_back({v[i],w[i]});
            rraph[v[i]].push_back({u[i],w[i]});
        }
    }
    dijkstratrace(s);
    for(int i=1;i<=n;i++)
    {
        sort(trace[i].begin(),trace[i].end());
    }
    ll ans=INFINITE2;
    for(int i=1;i<=trace[t].size();i++)
    {
        dijkstralast(x,i);
        ans=min(ans,dlast[y]);
    }
    cout << ans << endl;
}

int main()
{
    fastIO
    //freopen("hanhhhh.inp","r",stdin);
    //freopen("hanhhhh.out","w",stdout);
    ll t=1;
    //cin >> t;
    while(t--)
    solve();
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(ll)':
commuter_pass.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for(int i=0;i<graph[u].size();i++)
      |                     ~^~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dijkstra1(ll)':
commuter_pass.cpp:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for(int i=0;i<graph[u].size();i++)
      |                     ~^~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dijkstratrace(ll)':
commuter_pass.cpp:119:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         for(int i=0;i<rraph[u].size();i++)
      |                     ~^~~~~~~~~~~~~~~~
commuter_pass.cpp:126:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |                 for(int i=0;i<trace[u].size();i++) trace[v].push_back(trace[u][i]++);
      |                             ~^~~~~~~~~~~~~~~~
commuter_pass.cpp:128:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |             else if(d[v]==d[u]+w) for(int i=0;i<trace[u].size();i++) trace[v].push_back(trace[u][i]++);
      |                                               ~^~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dijkstralast(ll, ll)':
commuter_pass.cpp:144:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |         for(int i=0;i<graph[u].size();i++)
      |                     ~^~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:201:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  201 |     for(int i=1;i<=trace[t].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~

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