Submission #207043

#	Time	Username	Problem	Language	Result	Execution time	Memory
207043		Saboon	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	1095 ms	9592 KiB

ho_t4

#include<bits/stdc++.h> 
using namespace std; 
  
const long long maxn = 210; 
const long long maxm = 5e4 + 10; 
const long long inf = 1e18; 
  
struct matrix{ 
    long long n, m; 
    long long a[maxn][maxn]; 
    matrix(long long N, long long M){ 
        n = N; 
        m = M; 
        for(long long i = 0; i < n; i++) 
            for(long long j = 0; j < m; j++) 
                a[i][j] = inf; 
    } 
    matrix operator * (matrix & oth){ 
        matrix ans = matrix(n, n); 
        for(long long i = 0; i < n; i++){ 
            for(long long j = 0; j < n; j++){ 
                ans.a[i][j] = min(a[i][j], oth.a[i][j]); 
                for(long long k = 0; k < n; k++) 
                    ans.a[i][j] = min(ans.a[i][j], a[i][k] + oth.a[k][j]); 
            } 
        } 
        return ans; 
    } 
}; 
  
long long n, m; 
long long from[maxm]; 
long long to[maxm]; 
long long D[maxm]; 
long long weight[maxm]; 
long long ans; 
matrix a = matrix(0, 0); 
matrix b = matrix(0, 0); 
multiset<long long> BOI[maxn][maxn]; 
  
void in(); 
void solve(); 
void rsolve(long long x); 
void out(); 
  
int main(){ 
    in(); 
    solve(); 
    out(); 
} 
  
void in(){ 
    ios::sync_with_stdio(false); 
    cout.tie(0); 
    cin.tie(0); 
    cin >> n >> m; 
    for(long long i = 0; i < m; i++){ 
        long long u, v, w, d; 
        cin >> u >> v >> w >> d; 
        u--; 
        v--; 
        from[i] = u; 
        to[i] = v; 
        D[i] = d; 
        weight[i] = w; 
        BOI[u][v].insert(w); 
    } 
} 
  
void solve(){ 
    ans = inf; 
    a = matrix(n, n); 
    for(long long i = 0; i < n; i++){ 
        for(long long j = 0; j < n; j++){ 
            BOI[i][j].insert(inf); 
            a.a[i][j] = *BOI[i][j].begin(); 
        } 
    } 
    b = a; 
    rsolve(0); 
    for(long long i = 0; i < m; i++){ 
        b = a; 
        long long u = from[i]; 
        long long v = to[i]; 
        BOI[u][v].erase(BOI[u][v].find(weight[i])); 
        BOI[v][u].insert(weight[i]); 
        b.a[u][v] = *BOI[u][v].begin(); 
        b.a[v][u] = *BOI[v][u].begin(); 
        rsolve(D[i]); 
        BOI[v][u].erase(BOI[v][u].find(weight[i])); 
        BOI[u][v].insert(weight[i]); 
    } 
    if(ans == inf) 
        ans = -1; 
} 
  
void rsolve(long long x){ 
    for(long long i = 0; i < 20; i++) 
        b = b * b; 
    ans = min(ans, b.a[0][n - 1] + b.a[n - 1][0] + x); 
} 
  
void out(){ 
    cout << ans; 
} 

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63