Submission #293841

#	Time	Username	Problem	Language	Result	Execution time	Memory
293841		BeanZ	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	544 ms	23400 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define endl '\n'
const int N = 1e5 + 5;
ll n, m;
ll d[N][4], dis[N];
vector<pair<ll, ll>> node[N];
void dijk(ll u, ll t){
        for (int i = 1; i <= n; i++) d[i][t] = 1e18;
        priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
        pq.push({0, u});
        d[u][t] = 0;
        while (pq.size()){
                pair<ll, ll> x = pq.top();
                pq.pop();
                if (x.first != d[x.second][t]) continue;
                for (auto j : node[x.second]){
                        if (d[j.first][t] > (x.first + j.second)){
                                d[j.first][t] = x.first + j.second;
                                pq.push({d[j.first][t], j.first});
                        }
                }
        }
        /*
        cout << u << ": ";
        for (int i = 1; i <= n; i++){
                cout << d[i][t] << " ";
        }
        cout << endl;
        */
}
bool cmp(ll u, ll v){
        return d[u][0] < d[v][0];
}
int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        if (fopen("balance.in", "r")){
                freopen("balance.in", "r", stdin);
                freopen("balance.out", "w", stdout);
        }
        cin >> n >> m;
        ll s, t, u, v;
        cin >> s >> t >> u >> v;
        for (int i = 1; i <= m; i++){
                ll u, v, c;
                cin >> u >> v >> c;
                node[u].push_back({v, c});
                node[v].push_back({u, c});
        }
        dijk(s, 0);
        dijk(t, 1);
        dijk(u, 2);
        dijk(v, 3);
        ll lim = d[t][0];
        ll ans = 1e18;
        vector<ll> now;
        for (int i = 1; i <= n; i++){
                now.push_back(i);
                dis[i] = d[i][2];
        }
        sort(now.begin(), now.end(), cmp);
        for (int i = 1; i <= n; i++){
                ll x = now[i - 1];
                //cout << x << ": ";
                for (auto j : node[x]){
                        //cout << j.first << " " << d[x][0] << " " << j.second << " " << d[j.first][1] << endl;
                        if ((d[x][0] + j.second + d[j.first][1]) == lim){
                                dis[j.first] = min(dis[j.first], dis[x]);
                        }
                }
                //cout << endl;
                //cout << dis[x] << " " << d[x][3] << " " << x << endl;
                ans = min(ans, dis[x] + d[x][3]);
        }
        now.clear();
        for (int i = 1; i <= n; i++){
                now.push_back(i);
                dis[i] = d[i][3];
        }
        sort(now.begin(), now.end(), cmp);
        for (int i = 1; i <= n; i++){
                ll x = now[i - 1];
                for (auto j : node[x]){
                        if ((d[x][0] + j.second + d[j.first][1]) == lim){
                                dis[j.first] = min(dis[j.first], dis[x]);
                        }
                }
                ans = min(ans, dis[x] + d[x][2]);
        }
        cout << ans;
}
/*
*/

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:42:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   42 |                 freopen("balance.in", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:43:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   43 |                 freopen("balance.out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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