Submission #1011471

#TimeUsernameProblemLanguageResultExecution timeMemory
1011471gutzzyShortcut (IOI16_shortcut)C++17
0 / 100
0 ms436 KiB
#include <bits/stdc++.h> using namespace std; const long long inf = 9223372036854775807; vector<vector<long long>> m; void floyd_warshall(int n){ for(int k=0;k<n;k++){ for(int i=0;i<2*n;i++){ for(int j=0;j<2*n;j++){ if((m[i][j]>m[i][k]+m[k][j]) and m[k][j]!=inf and m[i][k] != inf){ m[i][j] = m[i][k] + m[k][j]; } } } } return; } long long diam(vector<vector<long long>> &g, int n){ long long res = 0; for(int i=0;i<2*n;i++){ for(int j=i;j<2*n;j++){ res = max(res,g[i][j]); } } return res; } long long find_shortcut(int n, vector<int> l, vector<int> d, int c){ m = vector<vector<long long>> (2*n,vector<long long>(2*n,inf)); for(int i=0;i<2*n;i++) m[i][i] = 0; long long ans = inf; for(int i=0;i<n-1;i++){ m[i][i+1] = (long long) l[i]; m[i+1][i] = (long long) l[i]; } for(int i=0;i<n;i++){ m[i][n+i] = (long long) d[i]; m[n+i][i] = (long long) d[i]; } vector<vector<long long>> mm = m; for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ // express railroad entre i & j if(m[i][j]<=c) continue; m[i][j] = c; m[j][i] = c; floyd_warshall(n); ans = min(ans, diam(m,n)); m = mm; } } return ans; } /* int main(){ cout << find_shortcut(2, {5}, {3, 0}, 1) << endl; return 0; } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...