Submission #857640

#	Time	Username	Problem	Language	Result	Execution time	Memory
857640		yusufhocaoglu	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	412 ms	42444 KiB

commuter_pass

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
#define ll long long
#define pri pair<int,int>
#define prl pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pair<int,int>>
#define vpl vector<pair<ll,ll>>
#define re return 0
#define sqrt sqrtl
#define int ll

struct node {
    vector<pri> adj;
    int val;
    pri sx = {1e18,1e18},sy = {1e18,1e18};
};

pri compx(pri a, pri b) {
    if (a.first < b.first) return a;
    if (a.first==b.first) return a.second > b.second ? b : a;
    return b;
}

pri compy(pri a,pri b) {
    if (a.second < b.second) return a;
    if (a.second == b.second) return a.first < b.first ? a : b;
    return b;
}

int32_t main() {
    int n,m;cin>>n>>m;
    int s,t,u,v;cin>>s>>t>>u>>v;
    vector<node> nodes(n);
    for (int i = 0;i<m;i++) {
        int a,b,c;cin>>a>>b>>c;
        nodes[a-1].adj.push_back({b-1,c});
        nodes[b-1].adj.push_back({a-1,c});
    }
    /* for (int i = 0;i<n;i++) {
        cout<<i<<endl;
        for (int j = 0;j<nodes[i].adj.size();j++) {
            cout<<nodes[i].adj[j].first<<" "<<nodes[i].adj[j].second<<endl;
        }
    } */

    auto dijkstra = [n,nodes](int start) {
        vector<int> mp(n,1e18);
        mp[start] = 0;
        set<pri> q;
        q.insert({0,start});
        while (q.size()) {
            auto f = *q.begin();

            for (int i = 0;i<nodes[f.second].adj.size();i++) {
                if (mp[nodes[f.second].adj[i].first] > (mp[f.second] + nodes[f.second].adj[i].second)) {
                    mp[nodes[f.second].adj[i].first] = mp[f.second] + nodes[f.second].adj[i].second;
                    q.insert({mp[f.second] + nodes[f.second].adj[i].second,nodes[f.second].adj[i].first});
                }
            }

            q.erase(q.begin());
        }
        return mp;
    };

    vector<int> dijkS,dijkU,dijkV;
    dijkS = dijkstra(s-1);
    dijkU = dijkstra(u-1);
    dijkV = dijkstra(v-1);

    vector<pri> dijk(n);
    for (int i = 0;i<n;i++) {
        dijk[i] = {dijkS[i],i};
    }
    sort(dijk.begin(),dijk.end());
    nodes[s-1].sx = nodes[s-1].sy = {dijkU[s-1],dijkV[s-1]};
    for (int i = 0;i<dijk.size();i++) {
        for (int j = 0;j<nodes[dijk[i].second].adj.size();j++) {
            if (dijkS[nodes[dijk[i].second].adj[j].first] + nodes[dijk[i].second].adj[j].second == dijk[i].first) {
                nodes[dijk[i].second].sx = compx(nodes[dijk[i].second].sx,nodes[nodes[dijk[i].second].adj[j].first].sx);
                nodes[dijk[i].second].sy = compy(nodes[dijk[i].second].sy,nodes[nodes[dijk[i].second].adj[j].first].sy);
                //cout<<nodes[dijk[i].second].minY<<endl;
            }
        }
        nodes[dijk[i].second].sx.first = min(nodes[dijk[i].second].sx.first,dijkU[dijk[i].second]);
        nodes[dijk[i].second].sy.first = min(nodes[dijk[i].second].sy.first,dijkU[dijk[i].second]);
        nodes[dijk[i].second].sx.second = min(nodes[dijk[i].second].sx.second,dijkV[dijk[i].second]);
        nodes[dijk[i].second].sy.second = min(nodes[dijk[i].second].sy.second,dijkV[dijk[i].second]);
        //nodes[dijk[i].second].sx = nodes[dijk[i].second].sy = {dijkU[dijk[i].second],dijkV[dijk[i].second]};
    }
    /* for (int i = 0;i<n;i++) {
        cout<<i+1<<" -> "<<endl;
        cout<<" "<<nodes[i].sx.first<<" "<<nodes[i].sx.second<<endl;
        cout<<" "<<nodes[i].sy.first<<" "<<nodes[i].sy.second<<endl;
    } */
    int va = nodes[t-1].sx.first + nodes[t-1].sx.second;
    int vb = nodes[t-1].sy.first + nodes[t-1].sy.second;
    cout<<min(min(va,vb),dijkU[v-1])<<endl;
    
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In lambda function:
commuter_pass.cpp:59:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |             for (int i = 0;i<nodes[f.second].adj.size();i++) {
      |                            ~^~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'int32_t main()':
commuter_pass.cpp:82:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for (int i = 0;i<dijk.size();i++) {
      |                    ~^~~~~~~~~~~~
commuter_pass.cpp:83:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for (int j = 0;j<nodes[dijk[i].second].adj.size();j++) {
      |                        ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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