oj.uz

답안 #211542

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
211542 2020-03-20T17:00:06 Z kshitij_sodani Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 45 ms 2688 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef  long long 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 yes[201][201];
map<pair<llo,llo>,llo> dob;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	llo n,m;
	memset(dis,-1,sizeof(dis));
	memset(yes,0,sizeof(yes));
	cin>>n>>m;

	llo ac,bb,cc,dd;
	
	for(llo i=0;i<m;i++){
		cin>>ac>>bb>>cc>>dd;
		adj[ac-1].pb({bb-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]);
					}
				}
			}
		}
	}
	
	llo ans=-1;
	if(dis[0][n-1]>-1 and dis[n-1][0]>-1){
		ans=dis[0][n-1]+dis[n-1][0];
	}
	priority_queue<pair<llo,llo>> cd;
	llo dist3[n];
	pair<llo,llo> par[n];
	for(llo i=0;i<n;i++){
		dist3[i]=-1;
	}
	dist3[0]=0;
	cd.push({0,0});

	while(!cd.empty()){
		pair<llo,llo> bb=cd.top();
		cd.pop();
		bb.a=-bb.a;
		for(int k=0;k<adj[bb.b].size();k++){
			pair<int,int> jj=adj[bb.b][k];
			if(dist3[jj.a]==-1 or dist3[jj.a]>bb.a+jj.b ){
				dist3[jj.a]=bb.a+jj.b;
				cd.push({-dist3[jj.a],jj.a});
				par[jj.a]={bb.b,k};
			}
		}
	}
	llo tot5=0;
	if(dist3[n-1]>-1){
		llo nn=n-1;
		while(nn!=0){
			yes[par[nn].a][par[nn].b]=1;
			nn=par[nn].a;
			tot5+=1;
		}
	}
	pair<llo,llo> par2[n];

	llo dist4[n];

	for(llo i=0;i<n;i++){
		dist4[i]=-1;
	}
	dist4[n-1]=0;
	cd.push({0,n-1});

	while(!cd.empty()){
		pair<llo,llo> bb=cd.top();
		cd.pop();

		bb.a=-bb.a;
//		cout<<bb.b<<" "<<bb.a<<endl;
		for(int k=0;k<adj[bb.b].size();k++){
			pair<int,int> jj=adj[bb.b][k];
			if(dist4[jj.a]==-1 or dist4[jj.a]>bb.a+jj.b ){
				dist4[jj.a]=bb.a+jj.b;
				cd.push({-dist4[jj.a],jj.a});
				par[jj.a]={bb.b,k};
			}
		}
	}
	if(dist4[0]>-1){
		llo nn=0;
		while(nn!=n-1){
			yes[par[nn].a][par[nn].b]=1;
			nn=par[nn].a;
			tot5+=1;
		}
	}

	for(llo i=0;i<n;i++){
		for(llo j=0;j<adj[i].size();j++){
			llo nn=adj[i][j].a;
			if(yes[i][j]==0){
				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]);
				}
			}
			else{
				continue;
				priority_queue<pair<llo,llo>> cc;
				llo dist[n];
				for(llo i=0;i<n;i++){
					dist[i]=-1;
				}
				dist[0]=0;
				cc.push({0,0});
				while(!cc.empty()){
					pair<llo,llo> bb=cc.top();
					cc.pop();

					bb.a=-bb.a;
			//		cout<<bb.b<<" "<<bb.a<<endl;
					for(auto jj:adj[bb.b]){
						if(dist[jj.a]==-1 or dist[jj.a]>bb.a+jj.b ){
							if(bb.b!=i or jj.a!=nn){
								dist[jj.a]=bb.a+jj.b;
								cc.push({-dist[jj.a],jj.a});
							}
						}
					}
					if(bb.b==nn){
						if(dist[i]==-1 or dist[i]>dist[bb.b]+adj[i][j].b){
							dist[i]=dist[bb.b]+adj[i][j].b;
							cc.push({-dist[i],i});
						}
					}
				}
				llo dist2[n];
				for(llo i=0;i<n;i++){
					dist2[i]=-1;
				}
				dist2[n-1]=0;
				cc.push({0,n-1});
				while(!cc.empty()){
					pair<llo,llo> bb=cc.top();
					cc.pop();
					bb.a=-bb.a;
					for(auto jj:adj[bb.b]){
						if(dist2[jj.a]==-1 or dist2[jj.a]>bb.a+jj.b ){
							if(bb.b!=i or jj.a!=nn){
								dist2[jj.a]=bb.a+jj.b;
								cc.push({-dist2[jj.a],jj.a});
							}
						}
					}
					if(bb.b==nn){
						if(dist2[i]==-1 or dist2[i]>dist2[bb.b]+adj[i][j].b){
							dist2[i]=dist2[bb.a]+adj[i][j].b;
							cc.push({-dist2[i],i});
						}
					}
				}
				if(dist[n-1]>-1 and dist2[0]>-1){
					if(ans==-1){
						ans=dist[n-1]+dist2[0]+cost[i][j];
					}
					ans=min(ans,dist[n-1]+dist2[0]+cost[i][j]);
				}
			}
		}
	}
	cout<<ans<<endl;



	return 0;
}

Compilation message

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:70:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k=0;k<adj[bb.b].size();k++){
               ~^~~~~~~~~~~~~~~~~
ho_t4.cpp:104:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k=0;k<adj[bb.b].size();k++){
               ~^~~~~~~~~~~~~~~~~
ho_t4.cpp:123:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(llo j=0;j<adj[i].size();j++){
               ~^~~~~~~~~~~~~~
ho_t4.cpp:88:16: warning: unused variable 'par2' [-Wunused-variable]
  pair<llo,llo> par2[n];
                ^~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 896 KB Output is correct
2 Correct 13 ms 768 KB Output is correct
3 Correct 20 ms 896 KB Output is correct
4 Correct 19 ms 896 KB Output is correct
5 Correct 6 ms 896 KB Output is correct
6 Correct 19 ms 896 KB Output is correct
7 Correct 5 ms 768 KB Output is correct
8 Correct 5 ms 768 KB Output is correct
9 Correct 6 ms 896 KB Output is correct
10 Correct 16 ms 896 KB Output is correct
11 Correct 20 ms 896 KB Output is correct
12 Incorrect 17 ms 896 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 2688 KB Output is correct
2 Correct 41 ms 2664 KB Output is correct
3 Correct 43 ms 2640 KB Output is correct
4 Correct 16 ms 896 KB Output is correct
5 Correct 22 ms 896 KB Output is correct
6 Correct 20 ms 896 KB Output is correct
7 Correct 13 ms 896 KB Output is correct
8 Incorrect 5 ms 768 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 896 KB Output is correct
2 Correct 14 ms 896 KB Output is correct
3 Correct 38 ms 2048 KB Output is correct
4 Correct 14 ms 768 KB Output is correct
5 Correct 39 ms 2560 KB Output is correct
6 Correct 5 ms 768 KB Output is correct
7 Correct 5 ms 928 KB Output is correct
8 Incorrect 38 ms 2688 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 896 KB Output is correct
2 Correct 13 ms 768 KB Output is correct
3 Correct 20 ms 896 KB Output is correct
4 Correct 19 ms 896 KB Output is correct
5 Correct 6 ms 896 KB Output is correct
6 Correct 19 ms 896 KB Output is correct
7 Correct 5 ms 768 KB Output is correct
8 Correct 5 ms 768 KB Output is correct
9 Correct 6 ms 896 KB Output is correct
10 Correct 16 ms 896 KB Output is correct
11 Correct 20 ms 896 KB Output is correct
12 Incorrect 17 ms 896 KB Output isn't correct
13 Halted 0 ms 0 KB -