Submission #1303092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303092		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{
    int u, v, w, d;
};

vector <edge> e;
ll dist[202][202]; 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:33:20: error: 'graph' does not name a type
   33 | ll dist[202][202]; graph[202][202], se[202][202];
      |                    ^~~~~
ho_t4.cpp: In function 'void floyd()':
ho_t4.cpp:40:51: error: 'graph' was not declared in this scope; did you mean 'isgraph'?
   40 |         for(int j = 1; j <= n; j ++) dist[i][j] = graph[i][j];
      |                                                   ^~~~~
      |                                                   isgraph
ho_t4.cpp: In function 'void solve()':
ho_t4.cpp:72:12: error: 'graph' was not declared in this scope; did you mean 'isgraph'?
   72 |     memset(graph, 0x3f3f3f3f, sizeof(graph));
      |            ^~~~~
      |            isgraph
ho_t4.cpp:73:12: error: 'se' was not declared in this scope; did you mean 'ee'?
   73 |     memset(se, 0x3f3f3f3f, sizeof(se));
      |            ^~
      |            ee
ho_t4.cpp:81:15: warning: narrowing conversion of 'u' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   81 |         e.pb({u, v, w, d});
      |               ^
ho_t4.cpp:81:18: warning: narrowing conversion of 'v' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   81 |         e.pb({u, v, w, d});
      |                  ^
ho_t4.cpp:81:21: warning: narrowing conversion of 'w' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   81 |         e.pb({u, v, w, d});
      |                     ^
ho_t4.cpp:81:24: warning: narrowing conversion of 'd' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   81 |         e.pb({u, v, w, d});
      |                        ^
ho_t4.cpp:118:23: error: 'prevv' was not declared in this scope; did you mean 'prevu'?
  118 |         graph[v][u] = prevv;
      |                       ^~~~~
      |                       prevu
ho_t4.cpp: At global scope:
ho_t4.cpp:127:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  127 | main(){
      | ^~~~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:132:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |         freopen("ZIP.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
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.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~