oj.uz

Submission #228510

# Submission time Handle Problem Language Result Execution time Memory
228510 2020-05-01T10:33:40 Z dvdg6566 Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 105 ms 4392 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define emp emplace
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end()
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MAXN = 210;
const int MAXE = 50100;
const ll INF = 1e9;
const ll MOD = 1e9+7;

typedef pair<pi,pi> pp;
typedef pair<int,pi> pip;
vector<vector<pip>> V,O,S;
vi f1,fn,b1,bn;
int N,E,a,b,w,r;
int U[MAXE];
int l[MAXN];
vector<pp> Edge;
priority_queue<pi,vpi,greater<pi>>pq;
int BLOCK=-1;

void dijkstra(int x, vector<vector<pip>> &A, vi &D){
	// cout<<x<<'\n';
	D.resize(N+1);
	for(int i=1;i<=N;++i)D[i]=INF;
	D[x]=0;
	pq.emp(0,x);
	while(SZ(pq)){
		pi t=pq.top();pq.pop();
		int n=t.s;int d=t.f;
		if(D[n]>d)continue;
		if(n!=x)U[l[n]]=1;
		for(auto t:A[n]){
			int c=t.f;int nd=d+t.s.f;
			if(nd>=D[c])continue;
			if(t.s.s==BLOCK)continue;
			D[c]=nd;
			l[c]=t.s.s;
			pq.emp(nd,c);
		}
	}
}

int main(){
	cin>>N>>E;
	V.resize(N+1);O.resize(N+1);S.resize(N+1);
	for (int i=0;i<E;++i){
		cin>>a>>b>>w>>r;
		V[a].pb(b, mp(w,i));
		O[b].pb(a, mp(w,i));
		Edge.pb(mp(a,b),mp(w,r));
	}
	dijkstra(1,V,f1);
	dijkstra(N,V,fn);
	dijkstra(1,O,b1);
	dijkstra(N,O,bn);
	// for (int i=0;i<E;++i)cout<<U[i]<<' ';cout<<'\n';
	int ans=f1[N]+bn[1];
	// cout<<ans<<'\n';
	for(int i=0;i<E;++i)if(U[i]){
		S[Edge[i].f.f].pb(Edge[i].f.s, mp(Edge[i].s.f, i));
	}
	for(int i=0;i<E;++i)if(!U[i]){
		int a=Edge[i].f.f;int b=Edge[i].f.s;int w=Edge[i].s.f;
		int forward=min(f1[N],f1[b]+w+bn[a]);
		int back=min(fn[1],fn[b]+w+b1[a]);
		int tw=Edge[i].s.s+forward+back;
		ans=min(ans,tw);
	}
	for (int i=0;i<E;++i)if(U[i]){
		int a=Edge[i].f.f;int b=Edge[i].f.s;int w=Edge[i].s.f;
		BLOCK=i;
		vi d1,d2;
		S[b].pb(a,mp(w,0));
		dijkstra(1,S,d1);dijkstra(N,S,d2);
		int tw=Edge[i].s.s+d1[N]+d2[1];
		// cout<<tw<<'\n';
		ans=min(ans,tw);
		S[b].pop_back();
	}
	cout<<ans;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 105 ms 4392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

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

Subtask #4
0 / 63.0

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