Submission #1016024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016024		abushbandit_	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	914 ms	7120 KiB

ho_t4

/*
 
author : abushbandit
contest : ---
 
*/

#pragma GCC optimize("Ofast,unroll-loops")

#include "bits/stdc++.h"
 
using namespace std;
 
#define int long long

const int INF = 1e15,N = 500;

int dis[N + 1];
int n;
int f[N + 1][N + 1];
multiset<pair<int,int>> g[N + 1];
 
int dist(int x,int tar){
	set<pair<int,int>> q;
	for(int i = 1;i <= n;i++) dis[i] = INF;
    q.insert({0, x});
    dis[x] = 0;
    while(!q.empty()){
        auto [val,u] = *q.begin();
        q.erase(q.begin());
        if(val > dis[u]) continue;
        for(auto [v, w] : g[u]){
            if(dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                q.insert({dis[v], v});
            }
        }
    }
    return dis[tar];
}
void solve() {
	
	int m;
	cin >> n >> m; 
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= n;j++){
			f[i][j] = INF;
			f[i][i] = 0;
		}
	}
	int cnt = 0;
	int a[m],b[m],c[m],d[m];
	for(int i = 0;i < m;i++){
		cin >> a[i] >> b[i] >> c[i] >> d[i];
		cnt += c[i] == 0;
		f[a[i]][b[i]] = min(c[i],f[a[i]][b[i]]);
		g[a[i]].insert({b[i],c[i]});
	}
	for(int k = 1; k <= n; ++k){
		for(int i = 1; i <= n; ++i){
			for(int j = 1; j <= n; ++j){
				f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
			}
		}
	}
	int ans = f[1][n] + f[n][1];
	for(int i = 0;i < m;i++){
		int cur = min(f[1][n], f[1][b[i]] + f[a[i]][n] + c[i]) + min(f[n][1], f[n][b[i]] + f[a[i]][1] + c[i]) + d[i];
		if(cur > ans){
			continue;
		}
		cur = d[i];
		g[a[i]].erase(g[a[i]].find({b[i],c[i]}));
		g[b[i]].insert({a[i],c[i]});
		cur += dist(1,n) + dist(n,1);
		ans = min(ans,cur);
		g[a[i]].insert({b[i],c[i]});
		g[b[i]].erase(g[b[i]].find({a[i],c[i]}));
	}
	if(ans >= INF){
		ans = -1;
	}
	cout << ans << "\n";	
	
	
}
 
signed main() {
	
	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	
	int t = 1;
	//~ cin >> t;
	while(t--){
		solve();
	}
 
}

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