oj.uz

Submission #202608

# Submission time Handle Problem Language Result Execution time Memory
202608 2020-02-17T09:13:40 Z dndhk Olympic Bus (JOI20_ho_t4) C++14
11 / 100
 169 ms 3576 KB 
#include <bits/stdc++.h>

#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 200;
const int MAX_M = 50000;
const ll INF = 1e14;

int N, M;
vector<pii> gp[2][MAX_N+1];
int u[MAX_M+1], v[MAX_M+1];
ll d[MAX_M+1], c[MAX_M+1];
ll dp[2][2][MAX_N+1];

ll ans;
vector<int> vt;

int ST;

priority_queue<pll, vector<pll>, greater<pll> > pq;

bool vst[MAX_N+1];
int from[MAX_N+1];

void solve(int x, int y){
	for(int i=1; i<=N; i++){
		dp[x][y][i] = INF;
		vst[i] = false;
		from[i] = 0;
	}
	dp[x][y][ST] = 0;
	pq.push({0LL, (ll)ST});
	while(!pq.empty()){
		pll now = pq.top(); pq.pop();
		if(vst[now.second])	continue;
		vst[now.second] = true;
		if(from[now.second]!=0){
			vt.pb(from[now.second]);
		}
		for(pii p : gp[x][now.second]){
			if(dp[x][y][p.first]>dp[x][y][now.second] + c[p.second]){
				from[p.first] = now.second;
				dp[x][y][p.first] = dp[x][y][now.second] + c[p.second];
				pq.push({dp[x][y][p.first], p.first});
			}
		}
	}
}

bool chk[MAX_M+1];

vector<pii> gp2[MAX_N+1];

ll dp2[MAX_N+1], dp3[MAX_N+1];

void solve2(int x){
	for(int i=1; i<=N; i++){
		while(!gp2[i].empty())	gp2[i].pop_back();
		dp2[i] = dp3[i] = INF;
		vst[i] = false;
	}
	for(int i=1; i<=M; i++){
		if(i!=x){
			gp2[u[i]].pb({v[i], (int)c[i]});
		}else{
			gp2[v[i]].pb({u[i], (int)c[i]});
		}
	}
	pq.push({0LL, 1LL});
	dp2[1] = 0;
	while(!pq.empty()){
		pll now = pq.top(); pq.pop();
		if(vst[now.second])	continue;
		vst[now.second] = true;
		for(pii p : gp2[now.second]){
			if(dp2[p.first]>dp2[now.second] + (ll)p.second){
				dp2[p.first] = dp2[now.second] + (ll)p.second;
				pq.push({dp2[p.first], p.first});
			}
		}
	}
	for(int i=1; i<=N; i++)	vst[i] = false;
	pq.push({0LL, (ll)N});
	dp3[N] = 0;
	while(!pq.empty()){
		pll now = pq.top(); pq.pop();
		if(vst[now.second])	continue;
		vst[now.second] = true;
		for(pii p : gp2[now.second]){
			if(dp3[p.first]>dp3[now.second] + (ll)p.second){
				dp3[p.first] = dp3[now.second] + (ll)p.second;
				pq.push({dp3[p.first], p.first});
			}
		}
	}
	//cout<<x<<" "<<dp2[N]<<" "<<dp3[1]<<" "<<d[x]<<endl;
	ans = min(ans, dp2[N] + dp3[1] + d[x]);
}


int main(){
	scanf("%d%d", &N, &M);
	for(int i=1; i<=M; i++){
		scanf("%d%d%lld%lld", &u[i], &v[i], &c[i], &d[i]);
		gp[0][u[i]].pb({v[i], i});
		gp[1][v[i]].pb({u[i], i});
	}
	ST = 1; solve(0, 0); ST = N; solve(0, 1);
	ST = 1; solve(1, 0); ST = N; solve(1, 1);
	ans = dp[0][0][N] + dp[0][1][1];
	for(int i : vt){
		if(!chk[i]){
			solve2(i);
			chk[i] = true;
		}
	}
	/*for(int i=0; i<2; i++){
		for(int j=0; j<2; j++){
			for(int k=1; k<=N; k++){
				cout<<dp[i][j][k]<<" ";
			}
			cout<<endl;
		}
	}*/
	
	for(int i=1; i<=M; i++){
		if(!chk[i]){
			//solve2(i);
			ll dist = d[i];
			if(dp[0][0][u[i]]<=dp[0][0][v[i]])	dist+=dp[0][0][N];
			else	dist+=min(dp[0][0][N], dp[0][0][v[i]] + c[i] + dp[1][1][u[i]]);
			if(dp[0][1][u[i]]<=dp[0][1][v[i]])	dist+=dp[0][1][1];
			else	dist+=min(dp[0][1][1], dp[0][1][v[i]] + c[i] + dp[1][0][u[i]]);
			// cout<<u[i]<<" "<<v[i]<<" "<<c[i]<<" "<<d[i]<<endl;
			// cout<<dp[0][0][v[i]]<<" "<<dp[1][1][u[i]]<<" "<<dp[0][1][v[i]]<<" "<<dp[1][0][u[i]]<<endl;
			ans = min(ans, dist);
		}
	}
	if(ans>=INF){
		printf("-1");
	}else{
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:108:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
ho_t4.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%lld%lld", &u[i], &v[i], &c[i], &d[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 15 ms 504 KB Output is correct
4 Correct 16 ms 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 296 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Incorrect 23 ms 376 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 3320 KB Output is correct
2 Correct 164 ms 3320 KB Output is correct
3 Correct 164 ms 3400 KB Output is correct
4 Correct 17 ms 504 KB Output is correct
5 Correct 12 ms 376 KB Output is correct
6 Correct 6 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 128 ms 3320 KB Output is correct
10 Correct 118 ms 3320 KB Output is correct
11 Correct 147 ms 3320 KB Output is correct
12 Correct 146 ms 3320 KB Output is correct
13 Correct 141 ms 3320 KB Output is correct
14 Correct 132 ms 3576 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 376 KB Output is correct
2 Correct 6 ms 380 KB Output is correct
3 Correct 28 ms 2652 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 36 ms 3320 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 33 ms 3320 KB Output is correct
9 Correct 35 ms 3320 KB Output is correct
10 Incorrect 35 ms 3320 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 15 ms 504 KB Output is correct
4 Correct 16 ms 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 296 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Incorrect 23 ms 376 KB Output isn't correct
11 Halted 0 ms 0 KB -