Submission #1069894

#TimeUsernameProblemLanguageResultExecution timeMemory
1069894Hugo1729Commuter Pass (JOI18_commuter_pass)C++11
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; vector<pair<ll,ll>> adj[100001]; vector<ll> dijkstra(ll start){ vector<ll> dist(n+1, LLONG_MAX); // Dijkstra's algorithm using T = pair<long long, ll>; priority_queue<T, vector<T>, greater<T>> pq; dist[start] = 0; // The shortest path from a node to itself is 0 pq.push({0, start}); while (!pq.empty()) { const auto [cdist, node] = pq.top(); pq.pop(); if (cdist != dist[node]) { continue; } for (const pair<ll, ll> &i : adj[node]) { // If we can reach a neighbouring node faster, // we update its minimum distance if (cdist + i.first < dist[i.second]) { pq.push({dist[i.second] = cdist + i.first, i.second}); } } } return dist; } ll solve(ll n, ll m, ll a, ll b, ll c, ll d){ vector<ll> path1 = dijkstra(a),path2 = dijkstra(b),sus1=dijkstra(c),sus2=dijkstra(d); vector<ll> dp(n+1,LLONG_MAX/4),dp1(n+1,LLONG_MAX/4),dp2(n+1,LLONG_MAX/4); // vector<pair<ll,ll>> dp1(n+1,{LLONG_MAX,LLONG_MAX}),dp2(n+1,{LLONG_MAX,LLONG_MAX}); vector<pair<ll,ll>> elza; for(ll i=1;i<=n;i++){ if(path1[i]+path2[i]==path1[b])elza.push_back({path1[i],i}); } dp[a]=sus1[a]+sus2[a]; dp1[a]=sus1[a]; dp2[a]=sus2[a]; sort(elza.begin(),elza.end()); for(ll i=0;i<elza.size();i++){ ll v = elza[i].second; for(auto [cost, w] : adj[v]){ if(path1[v]+path2[v]==path1[b]&&path1[w]<path1[v]){ dp1[v]=min(dp1[w],sus1[v]); dp2[v]=min(dp2[w],sus2[v]); dp[v]=min(dp[v],dp[w]); } } for(auto [cost, w] : adj[v]){ if(path1[v]+path2[v]==path1[b]&&path1[w]<path1[v]){ dp[v]=min(dp[v],dp1[v]+sus2[v]); dp[v]=min(dp[v],dp2[v]+sus1[v]); } } // cout << v <<' ' << path1[v] << ": " << dp[v] << ' ' << dp1[v] << ' ' << dp2[v] << '\n'; } return min(dp[b],sus1[d]); } int main(){ cin.tie(0)->sync_with_stdio(0); ll n,m,a,b,c,d; cin >> n >> m >> a >> b >> c >> d; for(ll i=0;i<m;i++){ ll x,y,cost; cin >> x >> y >> cost; adj[x].push_back({cost,y}); adj[y].push_back({cost,x}); } cout << min(solve(n,m,a,b,c,d),solve(n,m,b,a,c,d)); // cout << '\n'; // for(ll i = 0;i<elza.size();i++)cout << elza[i].first << ' ' << elza[i].second << '\n'; // cout << '\n'; return 0; }

Compilation message (stderr)

commuter_pass.cpp: In function 'std::vector<long long int> dijkstra(ll)':
commuter_pass.cpp:7:21: error: 'n' was not declared in this scope; did you mean 'yn'?
    7 |     vector<ll> dist(n+1, LLONG_MAX);
      |                     ^
      |                     yn
commuter_pass.cpp:17:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |   const auto [cdist, node] = pq.top();
      |              ^
commuter_pass.cpp: In function 'll solve(ll, ll, ll, ll, ll, ll)':
commuter_pass.cpp:51:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(ll i=0;i<elza.size();i++){
      |                ~^~~~~~~~~~~~
commuter_pass.cpp:53:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |         for(auto [cost, w] : adj[v]){
      |                  ^
commuter_pass.cpp:61:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |         for(auto [cost, w] : adj[v]){
      |                  ^