Submission #374890

#	Time	Username	Problem	Language	Result	Execution time	Memory
374890		MasterTaster	Commuter Pass (JOI18_commuter_pass)	C++14	55 / 100	1303 ms	44520 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], dy[MAXN], p[MAXN], fw[MALON][MALON], ress=INF;
vector<ll> g[MAXN];
map<pii, ll> w;

void dijkstra(int s, ll d[])
{
    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;

    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;
                p[v]=u;
                pq.push({d[v], 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;
    }

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

        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);
    //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);
    //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*)':
commuter_pass.cpp:35:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for (int i=0; i<g[u].size(); i++)
      |                       ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:82:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |             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: 0 / 45