Submission #417298

#	Time	Username	Problem	Language	Result	Execution time	Memory
417298		AmineWeslati	Olympic Bus (JOI20_ho_t4)	C++14	16 / 100	79 ms	4812 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int>vi; 
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x),end(x)

typedef pair<int,int>pi;
#define fi first
#define se second

#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=b-1; i>=a; i--)

void IO() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin); 
    freopen("output.txt", "w", stdout);
#endif
}
//--------------------------------

void ckmin(int &x, int y){x=min(x,y);}

const int INF=1e9;
const int MX=5e4+10;

int N,M,U[MX],V[MX],W[MX],C[MX];

vector<pair<pi,int>>adj[MX];
void build(){
	FOR(i,1,N+1) adj[i].clear();
	FOR(i,0,M){
		int u=U[i],v=V[i],w=W[i];
		adj[u].pb({{v,w},i});
	}
}

int dist[MX];
int par[MX],par_idx[MX];
void dijkstra(int s){
	FOR(i,1,N+1) dist[i]=INF;
	dist[s]=0;

	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
	q.push({0,s});

	while(sz(q)){
		int u=q.top().se; 
		int d=q.top().fi;
		q.pop();

		if(dist[u]<d) continue;

		for(auto it: adj[u]){
			int v=it.fi.fi,w=it.fi.se,idx=it.se; 
			if(dist[v]>d+w){
				dist[v]=d+w; 
				par[v]=u; 
				par_idx[v]=idx;
				q.push({dist[v],v});
			}
		}
	}
}

vi chosen(MX,0);
int to1[MX],toN[MX],from1[MX],fromN[MX];
void precompute(){
	build();

	dijkstra(1);
	FOR(i,1,N+1) from1[i]=dist[i];

	int u=N; 
	while(dist[N]!=INF && u!=1){
		chosen[par_idx[u]]=1;
		u=par[u];
	}

	dijkstra(N);
	FOR(i,1,N+1) fromN[i]=dist[i];

	u=1;
	while(dist[1]!=INF && u!=N){
		chosen[par_idx[u]]=1;
		u=par[u];
	}
	

	FOR(i,0,M) swap(U[i],V[i]);
	build();
	FOR(i,0,M) swap(U[i],V[i]);

	dijkstra(1);
	FOR(i,1,N+1) to1[i]=dist[i];

	dijkstra(N);
	FOR(i,1,N+1) toN[i]=dist[i];
}

int main(){
	IO();

	cin>>N>>M;
	FOR(i,0,M) cin>>U[i]>>V[i]>>W[i]>>C[i];

	precompute();

	int ans=toN[1]+to1[N]; 
	FOR(i,0,M){
		if(chosen[i]){
			swap(U[i],V[i]); 
			build();
			swap(U[i],V[i]); 

			int x=C[i];
			dijkstra(1);
			x+=dist[N];
			dijkstra(N);
			x+=dist[1];
			ckmin(ans,x);
		}
		else{
			int u=U[i],v=V[i];
			swap(u,v);

			bool c1=(max(max(from1[u],toN[v]),fromN[1])!=INF),
			c2=(max(max(from1[N],to1[v]),fromN[u])!=INF),
			c3=(max(max(from1[u],toN[v]),max(fromN[u],to1[v]))!=INF);

			if(c1)
				ckmin(ans,from1[u]+W[i]+C[i]+toN[v]+fromN[1]);
			if(c2)
				ckmin(ans,from1[N]+fromN[u]+C[i]+W[i]+to1[v]);
			if(c3)
				ckmin(ans,from1[u]+W[i]+C[i]+toN[v]
					+fromN[u]+W[i]+to1[v]);
		}
	}

	if(ans>=INF) ans=-1;
	cout << ans << endl;
}

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