Submission #1303091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303091		monaxia	Olympic Bus (JOI20_ho_t4)	C++20	Compilation error	0 ms	0 KiB

ho_t4

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define pb push_back
#define ppb pop_back
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define vektor vector
#define ordered_set tree<pair <ll, ll>, null_type, less<pair <ll, ll>>, rb_tree_tag, tree_order_statistics_node_update>

using namespace std;
using namespace __gnu_pbds; 

using ll = long long;
using ull = unsigned long long;
using ld = long double;

constexpr ull Mod = 1e9 + 7;
constexpr ull sqr = 708;
constexpr ld EPS = 1e-12L;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll random_ll(ll l, ll r) {if (l > r) return -1; return uniform_int_distribution<ll>(l, r)(rng);}

struct edge{
    ll u, v, w, d;
};

vector <edge> e;
ll dist[202][202];
int graph[202][202], se[202][202];

int n, m;
ll ans = 1e18;

void floyd(){
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++) dist[i][j] = graph[i][j];
    
    for(int k = 1; k <= n; k ++){
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= n; j ++){
                if(dist[i][k] <= 1e9 && dist[k][j] <= 1e9) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
}

vector <edge> ee;

void findpath(int u, int v){
    if(dist[u][v] > 1e18) return;
    
    for(int i = u; i != v;){
        for(auto& [x, y, w, d] : e){
            if(i != x) continue;
            
            if(w + dist[u][x] + dist[y][v] == dist[u][v]){
                ee.pb({x, y, w, d});
                i = y;
                
                break;
            }
        }
    }
}

void solve(){
    memset(dist, 0x3f3f3f3f, sizeof(dist));
    memset(graph, 0x3f3f3f3f, sizeof(graph));
    memset(se, 0x3f3f3f3f, sizeof(se));
    
    cin >> n >> m;    
    
    for(int i = 1; i <= m; i ++){
        ll u, v, w, d;
        cin >> u >> v >> w >> d;
        
        e.pb({u, v, w, d});
        
        dist[u][v] = min(dist[u][v], w);
        graph[u][v] = min(graph[u][v], w);
        if(graph[u][v] != w) min(se[u][v], w);
    }
    
    for(int i = 1; i <= n; i ++) dist[i][i] = graph[i][i] = se[i][i] = 0;
    
    floyd();
    findpath(1, n);
    findpath(n, 1);
    
    for(auto& [u, v, w, d] : e){
        if(dist[1][u] + w + dist[v][n] == dist[1][n] || dist[n][u] + w + dist[v][1] == dist[n][1]){
            continue;
        }
        
        if(dist[1][v] + w + d + dist[u][n] < dist[1][n] || dist[n][v] + w + d + dist[u][1] < dist[n][1]) ee.pb({u, v, w, d});
    } 
    
    ans = dist[1][n] + dist[n][1];
    
    
    for(auto& [u, v, w, d] : ee){
        ll prevu = graph[u][v], prevv = graph[v][u];
        
        graph[v][u] = w + d;
        if(graph[u][v] == w){
            graph[u][v] = se[u][v];
        }
        
        floyd();
        
        ans = min(ans, dist[1][n] + dist[n][1]);
        
        graph[u][v] = prevu;
        graph[v][u] = prevv;
    }
    
    if(ans > 1e17) ans = -1;
    
    cout << ans;
}   

    
main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  
    
    if(fopen("ZIP.inp", "r")){
        freopen("ZIP.inp", "r", stdin);
        freopen("ZIP.out", "w", stdout);
    }

    // return 0;

    int t = 1;
    // cin >> t;

    while(t --){
        solve();
        cout << "\n";
    }

    cerr << "Code time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    return 0;
}


// Whose eyes are those eyes?

Compilation message (stderr)

ho_t4.cpp: In function 'void solve()':
ho_t4.cpp:85:26: error: no matching function for call to 'min(int&, ll&)'
   85 |         graph[u][v] = min(graph[u][v], w);
      |                       ~~~^~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from ho_t4.cpp:1:
/usr/include/c++/13/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
ho_t4.cpp:85:26: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll' {aka 'long long int'})
   85 |         graph[u][v] = min(graph[u][v], w);
      |                       ~~~^~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note:   template argument deduction/substitution failed:
ho_t4.cpp:85:26: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll' {aka 'long long int'})
   85 |         graph[u][v] = min(graph[u][v], w);
      |                       ~~~^~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61:
/usr/include/c++/13/bits/stl_algo.h:5775:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
 5775 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5775:5: note:   template argument deduction/substitution failed:
ho_t4.cpp:85:26: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   85 |         graph[u][v] = min(graph[u][v], w);
      |                       ~~~^~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
 5785 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note:   template argument deduction/substitution failed:
ho_t4.cpp:85:26: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   85 |         graph[u][v] = min(graph[u][v], w);
      |                       ~~~^~~~~~~~~~~~~~~~
ho_t4.cpp:86:33: error: no matching function for call to 'min(int&, ll&)'
   86 |         if(graph[u][v] != w) min(se[u][v], w);
      |                              ~~~^~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
ho_t4.cpp:86:33: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll' {aka 'long long int'})
   86 |         if(graph[u][v] != w) min(se[u][v], w);
      |                              ~~~^~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note:   template argument deduction/substitution failed:
ho_t4.cpp:86:33: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll' {aka 'long long int'})
   86 |         if(graph[u][v] != w) min(se[u][v], w);
      |                              ~~~^~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5775:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
 5775 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5775:5: note:   template argument deduction/substitution failed:
ho_t4.cpp:86:33: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   86 |         if(graph[u][v] != w) min(se[u][v], w);
      |                              ~~~^~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
 5785 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note:   template argument deduction/substitution failed:
ho_t4.cpp:86:33: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   86 |         if(graph[u][v] != w) min(se[u][v], w);
      |                              ~~~^~~~~~~~~~~~~
ho_t4.cpp: At global scope:
ho_t4.cpp:128:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  128 | main(){
      | ^~~~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:133:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |         freopen("ZIP.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
ho_t4.cpp:134:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |         freopen("ZIP.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~