Submission #857575

#	Time	Username	Problem	Language	Result	Execution time	Memory
857575		yusufhocaoglu	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	2089 ms	44772 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;
};

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);

    int disT = dijkS[t-1];
    auto dfs = [disT,nodes,dijkU,dijkV,t,dijkS](int a, int prev, int length, int minX, int minY,auto&& dfs)->int {
        if (length==disT && a==t-1) return minX+minY;
        if (length>dijkS[a] || length>=disT) return 1e18;
        int mn = 1e18;
        for (int i = 0;i<nodes[a].adj.size();i++) {
            if (nodes[a].adj[i].first == prev) continue;
            mn = min(mn,dfs(nodes[a].adj[i].first,a,length+nodes[a].adj[i].second,min(minX,dijkU[nodes[a].adj[i].first]),min(minY,dijkV[nodes[a].adj[i].first]),dfs));
        }
        return mn;
    };

    cout<<min(dfs(s-1,-1,0,dijkU[s-1],dijkV[s-1],dfs),dijkU[v-1])<<endl;
    
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In lambda function:
commuter_pass.cpp:46: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]
   46 |             for (int i = 0;i<nodes[f.second].adj.size();i++) {
      |                            ~^~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp: In instantiation of 'main()::<lambda(long long int, long long int, long long int, long long int, long long int, auto:23&&)> [with auto:23 = main()::<lambda(long long int, long long int, long long int, long long int, long long int, auto:23&&)>&]':
commuter_pass.cpp:75:53:   required from here
commuter_pass.cpp:68: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]
   68 |         for (int i = 0;i<nodes[a].adj.size();i++) {
      |                        ~^~~~~~~~~~~~~~~~~~~~

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