oj.uz

Submission #374889

# Submission time Handle Problem Language Result Execution time Memory
374889 2021-03-08T13:02:22 Z MasterTaster Commuter Pass (JOI18_commuter_pass) C++14
24 / 100
 2000 ms 170336 KB 
#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

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
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1317 ms 43328 KB Output is correct
2 Execution timed out 2037 ms 170144 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2060 ms 170336 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 7332 KB Output is correct
2 Correct 35 ms 3564 KB Output is correct
3 Correct 35 ms 3564 KB Output is correct
4 Correct 124 ms 11116 KB Output is correct
5 Correct 67 ms 7020 KB Output is correct
6 Correct 36 ms 3692 KB Output is correct
7 Correct 37 ms 3820 KB Output is correct
8 Correct 38 ms 3980 KB Output is correct
9 Correct 39 ms 3692 KB Output is correct
10 Correct 66 ms 7276 KB Output is correct
11 Correct 35 ms 3436 KB Output is correct
12 Correct 34 ms 3436 KB Output is correct
13 Correct 35 ms 3564 KB Output is correct
14 Correct 35 ms 3564 KB Output is correct
15 Correct 38 ms 3564 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1317 ms 43328 KB Output is correct
2 Execution timed out 2037 ms 170144 KB Time limit exceeded
3 Halted 0 ms 0 KB -