Submission #170531

#	Time	Username	Problem	Language	Result	Execution time	Memory
170531		Akashi	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	554 ms	20820 KiB

commuter_pass

/**
          *
         * *
        * * *
       * * * *
         * *
        * * *
       * * * *
      * * * * *
     . * * * . *
       * . O *
      * O . * *
     * * * * * *
    * + * * * * *
   * * o * * * * *
  * * * * * * * * *
        ######
        ######
        ######
        ######
        ######
        ######
**/
#include <bits/stdc++.h>
using namespace std;

int n, m, S, T, U, V;
long long ds[100005], dt[100005], du[100005], dv[100005];
bool viz[100005], viz2[100005];
vector <pair <int, int> > v[100005];

priority_queue < pair <long long, int> , vector <pair <long long, int> > , greater <pair <long long, int> > > pq;
void dijkstra(int nod, long long d[]){
    memset(viz, 0, sizeof(viz));
    memset(viz2, 0, sizeof(viz2));
    d[nod] = 0;
    viz[nod] = 1;
    pq.push({0, nod});

    while(!pq.empty()){
        int nod = pq.top().second;
        pq.pop();
        if(viz2[nod]) continue ;
        viz2[nod] = 1;

        for(auto it : v[nod]){
            if(d[it.first] > d[nod] + it.second){
                d[it.first] = d[nod] + it.second;

                viz[it.first] = 1;
                pq.push({d[it.first], it.first});
            }
        }
    }
}

long long da[100005], db[100005], da2[100005], db2[100005];
long long Sol;
void solve(int S, int T, long long ds[], long long dt[], long long da[], long long db[]){
    memset(viz, 0, sizeof(viz));
    memset(viz2, 0, sizeof(viz2));

    pq.push({0, S});
    while(!pq.empty()){
        int nod = pq.top().second;
        pq.pop();

        if(viz2[nod]) continue ;
        viz2[nod] = 1;

        for(auto it : v[nod]){
            if(it.second + ds[nod] + dt[it.first] == ds[T]){
                Sol = min(Sol, db[nod] + du[it.first]);
                Sol = min(Sol, da[nod] + dv[it.first]);
                da[it.first] = min(da[it.first], da[nod]);
                db[it.first] = min(db[it.first], db[nod]);

                viz[it.first] = 1;
                pq.push({ds[it.first], it.first});
            }
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    scanf("%d%d", &S, &T);
    scanf("%d%d", &U, &V);

    int x, y, c;
    for(int i = 1; i <= m ; ++i){
        scanf("%d%d%d", &x, &y, &c);
        v[x].push_back({y, c});
        v[y].push_back({x, c});
    }

    for(int i = 1; i <= n ; ++i) ds[i] = dt[i] = du[i] = dv[i] = 1e18;

    dijkstra(S, ds);
    dijkstra(T, dt);
    dijkstra(U, du);
    dijkstra(V, dv);

    Sol = du[V];
//    for(int i = 1; i <= n ; ++i)
//        if(ds[i] + dt[i] == ds[T]) Sol = min(Sol, dv[i]);
    for(int i = 1; i <= n ; ++i){
        if(ds[i] + dt[i] == ds[T]){
            da[i] = du[i];
            db[i] = dv[i];
            Sol = min(Sol, da[i] + db[i]);
        }
        else da[i] = db[i] = 1e18;
        da2[i] = da[i];
        db2[i] = db[i];
    }

    solve(S, T, ds, dt, da, db);
    solve(T, S, dt, ds, da2, db2);

    for(int i = 1; i <= n ; ++i){
        if(ds[i] + dt[i] != ds[T]) continue ;

        for(auto it : v[i]){
            if(it.second + ds[i] + dt[it.first] == ds[T]){
                Sol = min(Sol, da[i] + db2[it.first]);
                Sol = min(Sol, db[i] + da2[it.first]);
            }
        }
    }

    printf("%lld", Sol);

    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &S, &T);
     ~~~~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &U, &V);
     ~~~~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &x, &y, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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