Submission #1035029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035029		_Nhm207_	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	212 ms	26752 KiB

commuter_pass

    #include<bits/stdc++.h>
    #define int long long
    #define Task "bus"

    using namespace std;

    const int N = 1e5 + 5;

    vector<int> ds , dt , du , dv;

    int n , m , u , v , s , t , ok[N];

    int res;

    vector<pair<int , int>> g[N];

    void dijkstra(int u , vector<int> &d){
        d . resize(n + 1);
        for(int i = 1 ; i <= n ; i++) d[i] = 1e18;
        d[u] = 0;
        priority_queue<pair<int , int> , vector<pair<int , int>> , greater<pair<int , int>>> pq;
        pq . push({d[u] , u});
        while(pq . size()){
            int u = pq . top() . second;
            int du = pq . top() . first;
            pq . pop();
            if(d[u] != du) continue;
            for(pair<int , int> nex : g[u]){
                if(d[nex . first] > d[u] + nex . second){
                    d[nex . first] = d[u] + nex . second;
                    pq . push({d[nex . first] , nex . first});
                }
            }
        }
    }

    void Get(int s , int t){
        vector<int> dp[2] , ds;
        dp[0] . resize(n + 1);
        dp[1] . resize(n + 1);
        ds . resize(n + 1); 
        for(int i = 0 ; i <= n ; i++) ds[i] = 1e18 , dp[0][i] = 1e18 , dp[1][i] = 1e18;
        ds[s] = 0;
        memset(ok , false , sizeof(ok));
        priority_queue<pair<int , pair<int , int>> , vector<pair<int , pair<int , int>>> , greater<pair<int , pair<int , int>>>> pq;
        pq . push({0 , {s , 0}});
        while(pq . size()){
            int u , par;
            int c = pq . top() . first;
            u = pq . top() . second . first;
            par = pq . top() . second . second;
            pq . pop();
            if(!ok[u]){
                dp[0][u] = min(dp[0][par] , du[u]);
                dp[1][u] = min(dp[1][par] , dv[u]);
                ok[u] = true;
                for(pair<int , int> nex : g[u]){
                    if(ds[nex . first] >= ds[u] + nex . second){
                        ds[nex . first] = ds[u] + nex . second;
                        pq . push({ds[nex . first] , {nex . first , u}});
                    }
                }
            }
            else if(c == ds[u] && min(dp[0][par] , du[u]) + min(dp[1][par] , dv[u]) <= dp[0][u] + dp[1][u]){
                dp[0][u] = min(dp[0][par] , du[u]);
                dp[1][u] = min(dp[1][par] , dv[u]);
            }
        }

        res = min(res , dp[0][t] + dp[1][t]);
    }


    int32_t main(){
        ios_base::sync_with_stdio(0);
        cin.tie(0);cout.tie(0);
        if(fopen(Task".inp","r")){
            freopen(Task".inp","r",stdin);
            freopen(Task".out","w",stdout);
        }
        cin >> n >> m;
        cin >> s >> t;
        cin >> u >> v;
        for(int i = 1 ; i <= m ; i++){
            int u , v , c;
            cin >> u >> v >> c;
            g[u] . push_back({v , c});
            g[v] . push_back({u , c});
        }
        dijkstra(u , du);
        dijkstra(v , dv);
        res = du[v];
        Get(s , t);
        Get(t , s);
        cout << res;
    }

Compilation message (stderr)

commuter_pass.cpp: In function 'int32_t main()':
commuter_pass.cpp:78:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |             freopen(Task".inp","r",stdin);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:79:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |             freopen(Task".out","w",stdout);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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