oj.uz

Submission #417305

# Submission time Handle Problem Language Result Execution time Memory
417305 2021-06-03T14:35:22 Z AmineWeslati Olympic Bus (JOI20_ho_t4) C++14
11 / 100
 76 ms 3756 KB 
#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=2e9;
	if(toN[1]!=INF && to1[N]!=INF) 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>=2e9) ans=-1;
	cout << ans << endl;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1740 KB Output is correct
2 Correct 1 ms 1740 KB Output is correct
3 Correct 3 ms 1740 KB Output is correct
4 Correct 4 ms 1740 KB Output is correct
5 Correct 3 ms 1740 KB Output is correct
6 Correct 2 ms 1740 KB Output is correct
7 Incorrect 1 ms 1612 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 3652 KB Output is correct
2 Correct 66 ms 3652 KB Output is correct
3 Correct 72 ms 3672 KB Output is correct
4 Correct 4 ms 1740 KB Output is correct
5 Correct 3 ms 1740 KB Output is correct
6 Correct 2 ms 1740 KB Output is correct
7 Correct 2 ms 1740 KB Output is correct
8 Correct 1 ms 1612 KB Output is correct
9 Correct 64 ms 3752 KB Output is correct
10 Correct 67 ms 3756 KB Output is correct
11 Correct 73 ms 3608 KB Output is correct
12 Correct 71 ms 3652 KB Output is correct
13 Correct 70 ms 3636 KB Output is correct
14 Correct 76 ms 3684 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1740 KB Output is correct
2 Incorrect 1 ms 1740 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1740 KB Output is correct
2 Correct 1 ms 1740 KB Output is correct
3 Correct 3 ms 1740 KB Output is correct
4 Correct 4 ms 1740 KB Output is correct
5 Correct 3 ms 1740 KB Output is correct
6 Correct 2 ms 1740 KB Output is correct
7 Incorrect 1 ms 1612 KB Output isn't correct
8 Halted 0 ms 0 KB -