Submission #374905

#	Time	Username	Problem	Language	Result	Execution time	Memory
374905		MasterTaster	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	1682 ms	46968 KiB

commuter_pass

#include <bits/stdc++.h>

#define pb push_back
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define xx first
#define yy second
#define MAXN 100010
#define INF 1000000000000000LL
#define MALON 310

using namespace std;

ll n, m, s, t, x, y, d[MAXN], ds[MAXN], dt[MAXN], dx[MAXN], dy[MAXN], p[MAXN], fw[MALON][MALON], minn[5][MAXN], minmin[MAXN], ress=INF;
vector<ll> g[MAXN];
map<pii, ll> w;

void dijkstra(int s, ll d[], int dal)
{
    for (int i=1; i<=n; i++) { d[i]=INF; p[i]=-1; }

    priority_queue< pll, vector<pll>, greater<pll> > pq;
    pq.push({0, s});
    d[s]=0;
    p[s]=-1;
    if (dal) minn[dal][s]=dx[s];

    while (!pq.empty())
    {
        ll td=pq.top().xx, u=pq.top().yy;
        pq.pop();

        if (td!=d[u]) continue;

        for (int i=0; i<g[u].size(); i++)
        {
            ll v, ww;
            v=g[u][i];
            pii par={u, v};
            ww=w[par];
            if (d[u]+ww<d[v])
            {
                d[v]=d[u]+ww;
                if (dal) { /*cout<<u<<" "<<v<<" "<<minn[dal][u]<<" "<<minn[dal][v]<<endl;*/ minn[dal][v]=min(minn[dal][u], dx[v]); /*cout<<"a sad "<<minn[dal][v]<<endl;*/ }
                p[v]=u;
                pq.push({d[v], v});
            }
            else if (dal && (d[u]+ww)==d[v]) { minn[dal][v]=min(minn[dal][u], min(minn[dal][v], dx[v])); }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin>>n>>m>>s>>t>>x>>y;

    for (int i=0; i<m; i++)
    {
        int u, v, ww; cin>>u>>v>>ww;
        g[u].pb(v);
        g[v].pb(u);
        w[{u, v}]=ww;
        w[{v, u}]=ww;
    }

    for (int i=1; i<=n; i++) { minn[1][i]=minn[2][i]=INF; }

    dijkstra(x, dx, 0); dijkstra(y, dy, 0); dijkstra(s, ds, 1); dijkstra(t, dt, 2);

    //cout<<"GLEEEEEEE "<<ds[t]<<endl;

    for (int i=1; i<=n; i++) { minmin[i]=min(minn[1][i], minn[2][i]); /*cout<<i<<" "<<minmin[i]<<endl;*/ }

    ress=dx[y];
    for (int i=1; i<=n; i++)
    {
        if (ds[i]+dt[i]==ds[t])
        {
            ress=min(ress, dy[i]+minmin[i]);
        }
    }
    cout<<ress;
    exit(0);

    if (s==x)
    {
        dijkstra(s, ds, 0); dijkstra(t, dt, 0); dijkstra(y, dy, 0);

        ress=ds[y];
        for (int i=1; i<=n; i++) if ((ds[i]+dt[i])==ds[t]) ress=min(ress, dy[i]);
        cout<<ress;
        exit(0);
    }

    if (n<=300)
    {
        for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) fw[i][j]=INF;

        for (int i=1; i<=n; i++)
        {
            fw[i][i]=0;
            for (int j=0; j<g[i].size(); j++) fw[i][g[i][j]]=w[{i, g[i][j]}];
        }

        for (int v=1; v<=n; v++)
            for (int i=1; i<=n; i++)
                for (int j=1; j<=n; j++)
                    fw[i][j]=min(fw[i][j], fw[i][v]+fw[v][j]);

        //for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) cout<<i<<" "<<j<<" "<<fw[i][j]<<endl;

        ress=fw[x][y];
        for (int i=1; i<=n; i++)
        {
            for (int j=1; j<=n; j++)
            {
                if (fw[s][i]+fw[i][j]+fw[j][t]==fw[s][t]) ress=min(ress, min(fw[x][i]+fw[j][y], fw[x][j]+fw[i][y]));
            }
        }
        cout<<ress;

        exit(0);
    }

    dijkstra(s, d, 0);
    //cout<<d[1]<<" "<<d[2]<<" "<<d[3]<<" "<<d[4]<<" "<<d[5]<<" "<<d[6]<<endl;

    int u=t;
    while(p[u]!=-1)///p[u] ili u?
    {
        //cout<<u<<" "<<p[u]<<endl;
        w[{u, p[u]}]=0;
        w[{p[u], u}]=0;
        u=p[u];
    }


    dijkstra(x, d, 0);
    //cout<<d[1]<<" "<<d[2]<<" "<<d[3]<<" "<<d[4]<<" "<<d[5]<<" "<<d[6];
    cout<<d[y];
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(int, long long int*, int)':
commuter_pass.cpp:36:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for (int i=0; i<g[u].size(); i++)
      |                       ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:104:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             for (int j=0; j<g[i].size(); j++) fw[i][g[i][j]]=w[{i, g[i][j]}];
      |                           ~^~~~~~~~~~~~

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