Submission #851653

#	Time	Username	Problem	Language	Result	Execution time	Memory
851653		sdfsdfsdf	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	2387 ms	262144 KiB

commuter_pass

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#define vt vector
#define heap priority_queue
#define dq deque
#define maxN 100005
#define maxM 5005
#define fi first
#define se second
#define For(i, j, n) for(int i=(j);i<=(n);i++)
#define pb push_back
#define pf push_front
#define reset(x,val) memset((x),(val),sizeof(x))
#define bit(i,j) ((i>>j)&1ll)
#define mask(i) (1ll<<i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define inf 1000000007 // mod for some cases
void io() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);}
typedef long long ll;
typedef pair<ll, ll> ii;
//type_here
struct pp
{
    ll u, dd;
};
struct pp2
{
    ll u, dd, t;
};
struct cmp
{
    bool operator()(pp a, pp b)
    {
        return a.dd>b.dd;
    };
};
struct cmp2
{
    bool operator()(pp2 a, pp2 b)
    {
        return a.dd>b.dd;
    }
};
heap <pp, vt<pp>, cmp> h;
heap <pp2, vt<pp2>, cmp2> h2;
ll n, m, d1[maxN], c1[maxN], d2[maxM][maxM];
map<ii, ll> d;
ll s, t, u, v;
ll ans, cnt;
vt<ll> a[maxN], w[maxN];
void dj1(ll s)
{
    reset(d1, inf);
    d1[s] = 0;
    h.push({s, d1[s]});
    while(!h.empty())
    {
        pp x = h.top(); h.pop();
        ll u = x.u;
        ll wee = x.dd;
        if (wee!=d1[u]) continue;
        for (int i=0;i<a[u].size();i++)
        {
            ll v = a[u][i], we = w[u][i];
            //cout<<u<<" "<<v<<endl;
            if (d1[v]>d1[u] + we)
            {
                d1[v]=d1[u] + we;
                c1[v]=1;
                h.push({v, d1[v]});
            }
            else if (d1[v]==d1[u] + we)
            {
                c1[v]++;
            }
        }
    }
}
void trace(ll u)
{
    if (u==s) {cnt--; return;}
    for (int i=0;i<a[u].size();i++)
    {
        ll v = a[u][i], we = w[u][i];
        if (d1[v]+we==d1[u])
        {
            d[{u, v}] = d[{v, u}] = cnt;
            //cout<<u<<" "<<v<<" "<<cnt<<" "<<00000<<endl;
            trace(v);
        }
    }
}
void dj2(ll s)
{
    reset(d2, inf);
    d2[s][0] = 0;
    h2.push({s, d2[s][0], 0});
    while(!h2.empty())
    {
        pp2 x = h2.top(); h2.pop();
        ll u = x.u;
        ll wee = x.dd;
        ll typ = x.t;
        if (d2[u][typ]!=wee) continue;
        For (i, 0, a[u].size()-1)
        {
            ll v = a[u][i], we = w[u][i];
            ll ntyp = d[{u, v}];
            For (ti, 1, ans)
            {
                if (ti==ntyp&&ntyp)
                {
                    if (d2[v][ntyp]>d2[u][typ])
                    {
                        d2[v][ntyp]=d2[u][typ];
                        h2.push({v, d2[v][ntyp], ntyp});
                    }
                }
                else
                {
                    if (d2[v][ti]>d2[u][typ]+we)
                    {
                        d2[v][ti]=d2[u][typ]+we;
                        h2.push({v, d2[v][ti]+we, ti});
                    }
                }
                //cout<<u<<" "<<v<<" "<<d2[v][ti]<<" "<<ti<<endl;
            }
        }
    }
}
void solve()
{
    cin>>n>>m;
    cin>>s>>t;
    cin>>u>>v;
    For (i, 1, m)
    {
        ll x, y, c;
        cin>>x>>y>>c;
        a[x].pb(y);
        a[y].pb(x);
        w[x].pb(c);
        w[y].pb(c);
    }
    dj1(s);
    cnt = ans = c1[t];
    //cout<<c1[t]<<endl;
    while(cnt)
    {
        trace(t);
    }
    //cout<<000000<<endl;
    dj2(u);
    ll res = inf;
    For (i, 0, ans)
    {
        res = min(res, d2[v][i]);
    }
    cout<<res<<endl;
}
signed main()
{
    io();
    solve();
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dj1(ll)':
commuter_pass.cpp:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for (int i=0;i<a[u].size();i++)
      |                      ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'void trace(ll)':
commuter_pass.cpp:84:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for (int i=0;i<a[u].size();i++)
      |                  ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'void dj2(ll)':
commuter_pass.cpp:11:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define For(i, j, n) for(int i=(j);i<=(n);i++)
      |                                     ^
commuter_pass.cpp:107:9: note: in expansion of macro 'For'
  107 |         For (i, 0, a[u].size()-1)
      |         ^~~

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