제출 #534519

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
534519		alvingogo	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	1053 ms	3036 KiB

ho_t4

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;

const long long inf=4.9e17;
struct eg{
	int v,c,d;
};
vector<vector<eg> > e;
vector<int> p[2];
vector<int> dz[2];
int n;
int dijk(int x,int y,int t){
	p_q<pair<int,int> > pq;
	vector<int> dis(n,inf);
	dis[x]=0;
	pq.push({0,x});
	while(!pq.empty()){
		auto h=pq.top();
		pq.pop();
		if(dis[h.sc]!=h.fs){
			continue;
		}
		for(auto a:e[h.sc]){
			if(dis[a.v]>dis[h.sc]+a.c){
				dis[a.v]=dis[h.sc]+a.c;
				if(t<2){
					p[t][a.v]=h.sc;
				}
				pq.push({dis[a.v],a.v});
			}
		}
	}
	if(t<2){
		dz[t]=dis;
	}
	return dis[y];
}
signed main(){
	AquA;
	int m;
	cin >> n >> m;
	e.resize(n);
	p[0].resize(n);
	p[1].resize(n);
	for(int i=0;i<m;i++){
		int u,v,c,d;
		cin >> u >> v >> c >> d;
		u--;
		v--;
		e[u].push_back({v,c,d});
	}
	vector<int> to[2];
	to[0].resize(n);
	to[1].resize(n);
	for(int i=0;i<n;i++){
		to[0][i]=dijk(i,n-1,2);
		to[1][i]=dijk(i,0,2);
	}
	int ans=0;
	ans+=dijk(0,n-1,0);
	ans+=dijk(n-1,0,1);
	/*
	for(int i=0;i<n;i++){
		cout << dz[0][i] << " ";
	}
	cout << "\n";
	for(int i=0;i<n;i++){
		cout << dz[1][i] << " ";
	}
	cout << "\n";
	for(int i=0;i<n;i++){
		cout << to[0][i] << " ";
	}
	cout << "\n";
	for(int i=0;i<n;i++){
		cout << to[1][i] << " ";
	}
	cout << "\n";
	cout << "\n";
	*/
	for(int i=0;i<n;i++){
		for(int j=0;j<e[i].size();j++){
			auto h=e[i][j];
			int yy=dz[0][n-1],kk=inf;
			if(dz[0][h.v]+h.c+h.d<dz[0][i]){
				yy=min(yy,dz[0][h.v]+h.c+h.d+to[0][i]);
				if(yy<dz[0][n-1]){
					if(p[1][h.v]==i){
						e[i][j].c+=h.d;
						kk=min(kk,yy+dijk(n-1,0,2));
						e[i][j].c-=h.d;
					}
					else{
						kk=min(kk,yy+dz[1][0]);
					}
				}
			}
			yy=dz[1][0];
			if(dz[1][h.v]+h.c+h.d<dz[1][i]){
				yy=min(yy,dz[1][h.v]+h.c+h.d+to[1][i]);
				//cout << to[1][i] << "\n";
				//cout << i << " " << h.v << " " << yy << "\n";
				if(yy<dz[1][0]){
					if(p[0][h.v]==i){
						e[i][j].c+=h.d;
						kk=min(kk,yy+dijk(0,n-1,2));
						e[i][j].c-=h.d;
					}
					else{
						kk=min(kk,yy+dz[0][n-1]);
					}
				}
			}
			ans=min(ans,kk);
		}
	}
	if(ans>=inf){
		cout << -1 << "\n";
	}
	else{
		cout << ans << "\n";
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:88:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<eg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   for(int j=0;j<e[i].size();j++){
      |               ~^~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63