Submission #374892

#	Time	Username	Problem	Language	Result	Execution time	Memory
374892		MasterTaster	Commuter Pass (JOI18_commuter_pass)	C++14	Compilation error	0 ms	0 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[MAXN], ress=INF;
vector<ll> g[MAXN];
map<pii, ll> w;

void dijkstra(int s, ll d[], bool 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[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) minn[v]=min(minn[u], dx[v]);
                p[v]=u;
                pq.push({d[v], v});
            }
            else if (dal && d[u]+ww==d[v]) minn[v]=min(minn[v], minn[u]);
        }
    }
}

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[i]=INF;

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

    ress=dx[y];
    for (int i=1; i<=n; i++)
    {
        if (ds[i]+dt[i]==ds[t])
        {
            ress=min(ress, dy[i]+minn[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);
    //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*, bool)':
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:100:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |             for (int j=0; j<g[i].size(); j++) fw[i][g[i][j]]=w[{i, g[i][j]}];
      |                           ~^~~~~~~~~~~~
commuter_pass.cpp:123:18: error: too few arguments to function 'void dijkstra(int, long long int*, bool)'
  123 |     dijkstra(s, d);
      |                  ^
commuter_pass.cpp:19:6: note: declared here
   19 | void dijkstra(int s, ll d[], bool dal)
      |      ^~~~~~~~
commuter_pass.cpp:136:18: error: too few arguments to function 'void dijkstra(int, long long int*, bool)'
  136 |     dijkstra(x, d);
      |                  ^
commuter_pass.cpp:19:6: note: declared here
   19 | void dijkstra(int s, ll d[], bool dal)
      |      ^~~~~~~~