Submission #1287856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287856		trinm01	Olympic Bus (JOI20_ho_t4)	C++20	0 / 100	44 ms	10028 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 f2[MAXN][2];
void dijsktra2(int s){
	priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> q;
	FOR(i, 1, n){
		f2[i][0]=f2[i][1]=oo;
	}
	f2[s][0]=0;
	q.push({0, {s, 0}});
	while(!q.empty()){
		int c=q.top().fi;
		auto uu=q.top().se;
		int u=uu.fi, t=uu.se;
		q.pop();
		if(c>f2[u][t]) continue;
		for(auto vv:adj[0][u]){
			int _=vv.u, v=vv.v, w=vv.c, d=vv.d, id=vv.id;
			if(f2[v][t]>c+w){
				f2[v][t]=c+w;
				q.push({f2[v][t], {v, t}});
			}
		}
		if(!t){
			for(auto vv:adj[1][u]){
				int _=vv.u, v=vv.v, w=vv.c, d=vv.d, id=vv.id;
				if(chk[id]) continue;
				if(f2[v][1]>c+w+d){
					f2[v][1]=c+w+d;
					q.push({f2[v][1], {v, 1}});
				}
			}
		}
	}
}
int f[5][MAXN];
void dijsktra(int s, int t, int tt){
	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(chk[id]) 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;
}

int solve(int s, int t){
    floyd();
    if(d[s][t]==oo) return oo;
    vector<int> trc=trace(s, t);
    // cout << d[s][t] << ' ';
    for(auto x:trc){
    	// cout << x << ' ';  
    	chk[x]=1;
    }
    dijsktra2(t);
    // cout << f2[s][0] << ' ';
    int ans=d[s][t]+min(f2[s][0], f2[s][1]);
    FOR(i, 1, m){
    	chk[i]=0;
    }
    dijsktra(t, 1, 0);
    dijsktra(s, 2, 1);
    for(auto x:trc){
    	auto vv=cc[x];
		int u=vv.u, v=vv.v, c=vv.c, d=vv.d, id=vv.id;
    	chk[x]=1;
    	dijsktra(s, 0, 0);
    	int cst=f[0][t]+f[1][u]+f[2][v]+c+d;
    	cst=min(cst, f[0][t]+f[1][v]+f[2][u]+c+d);
    	ans=min(ans, cst);
    	chk[x]=0;
    }
    return ans;
}

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});
    }
    
    int res;
    res=min(solve(1, n), solve(n, 1));
    // res=solve(1, n);
    if(res==oo) res=-1;
    cout << res;
    
    return 0;
}

Compilation message (stderr)

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

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