Submission #1086314

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086314		kiethm07	Commuter Pass (JOI18_commuter_pass)	C++11	100 / 100	225 ms	31436 KiB

commuter_pass

#include <bits/stdc++.h>

#define pii pair<int,int>
#define pli pair<long long,int>
#define iii pair<int,pii>
#define fi first
#define se second

#define vi vector<int>
#define vii vector<pii>
#define pb(i) push_back(i)
#define all(x) x.begin(),x.end()

#define TEXT "a"

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const ll inf = 1e15 + 5;
const ld eps = 1e-8;
const double pi = acos(-1);
const int N = 1e5 + 5;

vector<pii> a[N];
vector<int> b[N], c[N];
vector<ll> dS, dT, dX, dY;
ll f[N], g[N];
int n,m;
int s,t,x,y;

void dijkstra(int s, vector<ll>& d){
    d.resize(n + 5,inf);
    priority_queue<pli,vector<pli>,greater<pli>> pq;
    d[s] = 0;
    pq.push(pli(0,s));
    while(!pq.empty()){
        int u = pq.top().se;
        ll dis = pq.top().fi;
        pq.pop();
        if (dis > d[u]) continue;
        for (int i = 0; i < a[u].size(); i++){
            int v = a[u][i].fi;
            int w = a[u][i].se;
            if (d[u] + w < d[v]){
                d[v] = d[u] + w;
                pq.push(pli(d[v],v));
            }
        }
    }
}

void buildGraph(){
    for (int u = 1; u <= n; u++){
        for (int i = 0; i < a[u].size(); i++){
            int v = a[u][i].fi;
            int w = a[u][i].se;
            if (dS[v] == dS[u] + w && dS[t] == dS[u] + w + dT[v]){
                b[u].push_back(v);
                c[v].push_back(u);
                //cout << u << " " << v << " " << w << "\n";
            }
        }
    }
}

void calX(int u){
    if (f[u] != inf) return;
    f[u] = dX[u];
    for (int v : c[u]){
        calX(v);
        f[u] = min(f[u], f[v]);
    }
}

void calY(int u){
    if (g[u] != inf) return;
    g[u] = dY[u];
    for (int v : b[u]){
        calY(v);
        g[u] = min(g[u], g[v]);
    }
}

int main(){
    cin.tie(0) -> sync_with_stdio(0);
    if (fopen(TEXT".inp","r")){
        freopen(TEXT".inp","r",stdin);
        freopen(TEXT".out","w",stdout);
    }
    cin >> n >> m;
    cin >> s >> t >> x >> y;
    for (int i = 1; i <= m; i++){
        int u,v,w;
        cin >> u >> v >> w;
        a[u].pb(pii(v,w));
        a[v].pb(pii(u,w));
    }
    dijkstra(s, dS);
    dijkstra(t, dT);
    //cout << "-----\n";
    buildGraph();
    //cout << "-----\n";
    dijkstra(x, dX);
    dijkstra(y, dY);
    for (int i = 1; i <= n; i++) f[i] = g[i] = inf;
    calX(t);
    calY(s);
    ll res = dX[y];
    for (int i = 1; i <= n; i++){
        res = min(res,f[i] + g[i]);
    }
    for (int i = 1; i <= n; i++) f[i] = g[i] = inf;
    swap(x, y);
    swap(dX, dY);
    calX(t);
    calY(s);
    for (int i = 1; i <= n; i++){
        res = min(res,f[i] + g[i]);
    }
    cout << res << "\n";
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(int, std::vector<long long int>&)':
commuter_pass.cpp:44:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for (int i = 0; i < a[u].size(); i++){
      |                         ~~^~~~~~~~~~~~~
commuter_pass.cpp: In function 'void buildGraph()':
commuter_pass.cpp:57:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for (int i = 0; i < a[u].size(); i++){
      |                         ~~^~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:90:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         freopen(TEXT".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen(TEXT".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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