oj.uz

Submission #211204

# Submission time Handle Problem Language Result Execution time Memory
211204 2020-03-19T12:22:44 Z kshitij_sodani Olympic Bus (JOI20_ho_t4) C++17
11 / 100
 47 ms 3948 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef  int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
vector<pair<llo,llo>> adj[201];
vector<llo> cost[201];
llo dis[201][201];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	llo n,m;
	memset(dis,-1,sizeof(dis));

	cin>>n>>m;

	
	llo ac,bb,cc,dd;
//	vector<pair<pair<llo,llo>,pair<llo,llo>>> ed;
//	llo kk=1;
	
	for(llo i=0;i<m;i++){
		cin>>ac>>bb>>cc>>dd;
		adj[ac-1].pb({bb-1,cc});
		//ed.pb({{ac-1,bb-1},{cc,dd}});
		//adj2[bb-1].pb({ac-1,cc});
		cost[ac-1].pb(dd);
		if(dis[ac-1][bb-1]==-1){
			dis[ac-1][bb-1]=cc;
		}
		dis[ac-1][bb-1]=min(dis[ac-1][bb-1],cc);
	}
	for(llo i=0;i<n;i++){
		dis[i][i]=0;
	}
	for(llo k=0;k<n;k++){
		for(llo i=0;i<n;i++){
			for(llo j=0;j<n;j++){
				if(dis[i][k]!=-1 and dis[k][j]!=-1){
					if(dis[i][j]==-1){
						dis[i][j]=dis[i][k]+dis[k][j];
					}
					else{
						dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
					}
				}
			}
		}
	}
	/*priority_queue<pair<llo,llo>> aa;
	aa.push({0,0});
	llo dis[n];
	for(llo i=0;i<n;i++){
		dis[i]=-1;
	}
	dis[0]=0;
	while(!aa.empty()){
		pair<llo,llo> no=aa.top();
		aa.pop();
		no.a=-no.a;
		for(auto nn:adj[no.b]){
			if(dis[nn.a]==-1 or dis[nn.a]>no.a+nn.b){
				dis[nn.a]=no.a+nn.b;
				aa.push({-dis[nn.a],nn.a});
			}
		}
	}
	llo dis2[n];
	for(llo i=0;i<n;i++){
		dis2[i]=-1;
	}
	dis2[n-1]=0;
	aa.push({0,n-1});
	while(!aa.empty()){
		pair<llo,llo> no=aa.top();
		aa.pop();
		no.a=-no.a;
		for(auto nn:adj[no.b]){
			if(dis2[nn.a]==-1 or dis2[nn.a]>no.a+nn.b){
				dis2[nn.a]=no.a+nn.b;
				aa.push({-dis2[nn.a],nn.a});
			}
		}
	}
	llo dis3[n];
	for(llo i=0;i<n;i++){
		dis3[i]=-1;
	}
	dis3[0]=0;
	aa.push({0,0});
	while(!aa.empty()){
		pair<llo,llo> no=aa.top();
		aa.pop();
		no.a=-no.a;
		for(auto nn:adj2[no.b]){
			if(dis3[nn.a]==-1 or dis3[nn.a]>no.a+nn.b){
				dis3[nn.a]=no.a+nn.b;
				aa.push({-dis3[nn.a],nn.a});
			}
		}
	}
	llo dis4[n];
	for(llo i=0;i<n;i++){
		dis4[i]=-1;
	}
	dis4[n-1]=0;
	aa.push({0,n-1});
	while(!aa.empty()){
		pair<llo,llo> no=aa.top();
		aa.pop();
		no.a=-no.a;
		for(auto nn:adj2[no.b]){
			if(dis4[nn.a]==-1 or dis4[nn.a]>no.a+nn.b){
				dis4[nn.a]=no.a+nn.b;
				aa.push({-dis4[nn.a],nn.a});
			}
		}
	}*/

/*	cout<<ans<<endl;
	for(llo i=0;i<n;i++){
		cout<<dis[i]<<" ";
	}
	cout<<endl;
	for(llo i=0;i<n;i++){
		cout<<dis2[i]<<" ";
	}
	cout<<endl;
	for(llo i=0;i<n;i++){
		cout<<dis3[i]<<" ";
	}
	cout<<endl;
	for(llo i=0;i<n;i++){
		cout<<dis4[i]<<" ";
	}
	cout<<endl;*/
	llo ans=-1;
	if(dis[0][n-1]>-1 and dis[n-1][0]>-1){
		ans=dis[0][n-1]+dis[n-1][0];
	}
	for(llo i=0;i<n;i++){
		for(llo j=0;j<adj[i].size();j++){
			llo nn=adj[i][j].a;
			if(dis[i][0]>-1 and dis[0][n-1]>-1 and dis[n-1][nn]>-1){

				if(ans==-1){
					ans=dis[i][0]+cost[i][j]+dis[n-1][nn]+dis[0][n-1]+adj[i][j].b;
				}
				ans=min(ans,dis[i][0]+cost[i][j]+dis[n-1][nn]+dis[0][n-1]+adj[i][j].b);
			}
			if(dis[i][n-1]>-1 and dis[n-1][0]>-1 and dis[0][nn]>-1){

				if(ans==-1){
					ans=dis[i][n-1]+cost[i][j]+dis[0][nn]+dis[n-1][0]+adj[i][j].b;
				}
				ans=min(ans,dis[i][n-1]+cost[i][j]+dis[0][nn]+dis[n-1][0]+adj[i][j].b);
			}
			if(dis[0][nn]>-1 and dis[n-1][nn]>-1 and dis[i][0]>-1 and dis[i][n-1]>0){
				if(ans==-1){
					ans=dis[0][nn]+dis[n-1][nn]+dis[i][0]+dis[i][n-1]+adj[i][j].b*2+cost[i][j];
				}
				ans=min(ans,dis[0][nn]+dis[n-1][nn]+dis[i][0]+dis[i][n-1]+adj[i][j].b*2+cost[i][j]);
			}
		}
	}
	cout<<ans<<endl;










	return 0;
}

Compilation message

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:145:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(llo j=0;j<adj[i].size();j++){
               ~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 768 KB Output is correct
2 Correct 16 ms 512 KB Output is correct
3 Correct 20 ms 768 KB Output is correct
4 Correct 19 ms 768 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Correct 18 ms 640 KB Output is correct
7 Incorrect 5 ms 640 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 42 ms 2428 KB Output is correct
2 Correct 41 ms 2540 KB Output is correct
3 Correct 42 ms 2424 KB Output is correct
4 Correct 19 ms 768 KB Output is correct
5 Correct 19 ms 640 KB Output is correct
6 Correct 16 ms 640 KB Output is correct
7 Correct 15 ms 640 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 46 ms 2552 KB Output is correct
10 Correct 45 ms 3704 KB Output is correct
11 Correct 47 ms 3712 KB Output is correct
12 Correct 46 ms 3704 KB Output is correct
13 Correct 47 ms 3704 KB Output is correct
14 Correct 46 ms 3948 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 768 KB Output is correct
2 Correct 16 ms 640 KB Output is correct
3 Correct 35 ms 1920 KB Output is correct
4 Correct 16 ms 640 KB Output is correct
5 Correct 38 ms 2424 KB Output is correct
6 Incorrect 5 ms 640 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 768 KB Output is correct
2 Correct 16 ms 512 KB Output is correct
3 Correct 20 ms 768 KB Output is correct
4 Correct 19 ms 768 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Correct 18 ms 640 KB Output is correct
7 Incorrect 5 ms 640 KB Output isn't correct
8 Halted 0 ms 0 KB -