Submission #1288000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288000		trinm01	Olympic Bus (JOI20_ho_t4)	C++20	100 / 100	800 ms	9924 KiB

ho_t4

// #pragma GCC optimize("O3")
// #pragma GCC optimization("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;

#define int long long 
#define ll long long
#define FOR(i, l, r) for (int i = (l); i <= (r); i++)
#define FOD(i, r, l) for (int i = (r); i >= (l); i--)
#define fi first
#define se second
#define pii pair<int, int>

const ll mod = 1e9 + 7;
const int MAXN = 1e5 + 5;
const ll oo = 1e18 + 7;  
const int base = 10;

int n, m;
struct canh{
	int u, v, c, d, id;
}cc[MAXN];
vector<canh> adj[2][MAXN];

int chk[MAXN];

int f[5][MAXN], g[5][MAXN];
void dijsktra(int s, int t, int tt, int cam){
	priority_queue<pii, vector<pii>, greater<pii>> q;
	FOR(i, 1, n){
		f[t][i]=oo;
	}
	f[t][s]=0;
	q.push({0, s});
	while(!q.empty()){
		int c=q.top().fi, u=q.top().se;
		q.pop();
		if(c>f[t][u]) continue;
		for(auto vv:adj[tt][u]){
			int _=vv.u, v=vv.v, w=vv.c, d=vv.d, id=vv.id;
			if(id==cam) continue;
			if(f[t][v]>c+w){
				f[t][v]=c+w;
				q.push({f[t][v], v});
			}
		}
		for(auto vv:adj[1-tt][u]){
			int _=vv.u, v=vv.v, w=vv.c, d=vv.d, id=vv.id;
			if(id!=cam) continue;
			if(f[t][v]>c+w){
				f[t][v]=c+w;
				q.push({f[t][v], v});
			}
		}
	}
}
int d[205][205];
pii tr[205][205];
void floyd(){
	FOR(i, 1, n){
		FOR(j, 1, n){
			d[i][j]=oo;
			if(i==j) d[i][j]=0;
			tr[i][j]={0, 0};
		}
	}
	FOR(i, 1, m){
		auto vv=cc[i];
		int u=vv.u, v=vv.v, c=vv.c, dd=vv.d, id=vv.id;
		if(d[u][v]>c){
			d[u][v]=c;
			tr[u][v]={u, id};
		}
	}
	FOR(k, 1, n){
		FOR(u, 1, n){
			FOR(v, 1, n){
				if(d[u][v]>d[u][k]+d[k][v]){
					d[u][v]=d[u][k]+d[k][v];
					tr[u][v]=tr[k][v];
				}
			}
		}
	}
}
vector<int> trace(int s, int t){
	vector<int> trc;
	int u=t;
	while(u!=s){
		trc.push_back(tr[s][u].se);
		u=tr[s][u].fi;
	}
	reverse(trc.begin(), trc.end());
	return trc;
}

void pre(int s, int t){
    floyd();
    // cout << d[s][t] << ' ';
    if(d[s][t]==oo) return;
    vector<int> trc=trace(s, t);
    for(auto x:trc){
    	chk[x]=1;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    
     // freopen("test.txt", "r", stdin);
     // freopen("o2.out", "w", stdout);

    if(fopen(".inp", "r")){
        freopen(".inp", "r", stdin);
        freopen(".out", "w", stdout);
    }

    cin >> n >> m;
    FOR(i, 1, m){
    	int u, v, c, d;
    	cin >> u >> v >> c >> d;
    	cc[i]={u, v, c, d, i};
    	adj[0][u].push_back({0, v, c, d, i});
    	adj[1][v].push_back({0, u, c, d, i});
    }
    
    pre(1, n);
    pre(n, 1);
    
    dijsktra(1, 1, 0, 0);
    dijsktra(n, 2, 1, 0);
    dijsktra(n, 3, 0, 0);
    dijsktra(1, 4, 1, 0);
    FOR(i, 1, 4){
    	FOR(u, 1, n){
    		g[i][u]=f[i][u];
    	}
    }
    
    int res=oo;
    res=min(res, d[1][n]+d[n][1]);
    FOR(i, 1, m){
    	auto [u, v, c, dd, id]=cc[i];
		if(!chk[i]){
			int ton=min(d[1][n], g[1][v]+g[2][u]+c);
			int to1=min(d[n][1], g[3][v]+g[4][u]+c);
			// cout << ton << ' ' << g[3][v] << '\n';
			res=min(res, ton+to1+dd);
		}    	
		else{
			// cout << i << ' ';
			dijsktra(1, 1, 0, i);
		    dijsktra(n, 3, 0, i);
		    int ton=f[1][n];
			int to1=f[3][1];
			res=min(res, ton+to1+dd);
		}
    }
    
    if(res==oo) res=-1;
    cout << res;
    
    return 0;
}

Compilation message (stderr)

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:118:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |         freopen(".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
ho_t4.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         freopen(".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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