제출 #287126

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

ho_t4

#include <bits/stdc++.h>
using namespace std;

#define int long long
int n, m;
const int MXN = 205, MXM = 50005;

vector<pair<pair<int, int>, pair<int, int>>> eds; 
vector<pair<pair<int, int>, pair<int, int>>> adj[MXN]; 
int par[MXN];
int parof[MXN];
int dist1n[MXM];
int distn1[MXM];
int dist[MXN];
bool onpath[MXM];
bool onpath2[MXM];
vector<int> path;

int block = -1;
int mxh = INT_MAX * 200ll;

int get_dist(int src, int dest, int blo) {
	block = blo;
	memset(onpath, 0, sizeof onpath);
	for (int i=1; i<=n; i++) {
		dist[i] = mxh;
		par[i] = -1;
		parof[i] = -1;
	}
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> proc;
	proc.push({0, src});
	
	while (!proc.empty()) {
		pair<int, int> tr = proc.top();
		proc.pop();
		int no = tr.second;
		int di = tr.first;
		if (dist[no] < di) continue;
		dist[no] = di;
		
		for (auto x: adj[no]) {
			int ad = x.first.first;
			int ind = x.first.second;
			int we = x.second.first;
			if (ind == block) continue;
			if (dist[no] + we < dist[ad]) {
				dist[ad] = dist[no] + we;
				par[ad] = ind;
				parof[ad] = no;
				proc.push({dist[ad], ad});
			}
		}
	}
	
	vector<int> tr;
	tr.push_back(-1);
	path = tr;
	tr.clear();
	
	int x = dest;
	while (x != src) {
		if (x == -1) return dist[dest];
		tr.push_back(x);
		onpath[par[x]] = true;
		x = parof[x];
	}
	tr.push_back(src);
	reverse(tr.begin(), tr.end());
	
	path = tr;
	
	return dist[dest];
}

signed main() {

	cin >> n >> m;
	
	for (int i=0; i<m; i++) {
		int a, b, w, f;
		cin >> a >> b >> w >> f;
		adj[a].push_back({{b, i}, {w, f}});
		eds.push_back({{a, b}, {w, f}});
	}
	
	{
	
		int wh = get_dist(1, n, -1);
		dist1n[m] = wh;
		
		int apsp[n+1][n+1], apsp_exc[n+1][n+1];
		for (int i=1; i<=n; i++) {
			for (int j=1; j<=n; j++) {
				apsp[i][j] = mxh;
				apsp_exc[i][j] = mxh;
				if (i == j) apsp[i][j] = apsp_exc[i][j] = 0;
			}
		}
		for (int i=0; i<m; i++) {
			int a = eds[i].first.first, b = eds[i].first.second;
			int w = eds[i].second.first;
			apsp[a][b] = min(apsp[a][b], w);
			if (!onpath[i]) {
				apsp_exc[a][b] = min(apsp_exc[a][b], w);
			}
		}
		
		for (int k=1; k<=n; k++) {
			for (int i=1; i<=n; i++) {
				for (int j=1; j<=n; j++) {
					if (apsp[i][k] + apsp[k][j] < apsp[i][j]) {
						apsp[i][j] = apsp[i][k] + apsp[k][j];
					}
					if (apsp_exc[i][k] + apsp_exc[k][j] < apsp_exc[i][j]) {
						apsp_exc[i][j] = apsp_exc[i][k] + apsp_exc[k][j];
					}
				}
			}
		}
		
		
		
		for (int i=0; i<m; i++) {
			int a = eds[i].first.first, b = eds[i].first.second;
			int w = eds[i].second.first;
			if (onpath[i]) {
				dist1n[i] = mxh;
				if (path[0] != -1) {
					for (int i=0; i<path.size(); i++) {
						for (int j=i+1; j<path.size(); j++) {
							dist1n[i] = min(dist1n[i], apsp[1][path[i]] + apsp_exc[path[i]][path[j]] + apsp[path[j]][n]);
						}
					}
				}
			}
			else {
				dist1n[i] = wh;
				dist1n[i] = min(dist1n[i], apsp[1][b] + w + apsp[a][n]);
			}
		}
		
	}
	
	{
		
		int wh = get_dist(n, 1, -1);
		distn1[m] = wh;
		
		int apsp[n+1][n+1], apsp_exc[n+1][n+1];
		for (int i=1; i<=n; i++) {
			for (int j=1; j<=n; j++) {
				apsp[i][j] = mxh;
				apsp_exc[i][j] = mxh;
				if (i == j) apsp[i][j] = apsp_exc[i][j] = 0;
			}
		}
		for (int i=0; i<m; i++) {
			int a = eds[i].first.first, b = eds[i].first.second;
			int w = eds[i].second.first;
			apsp[a][b] = min(apsp[a][b], w);
			if (!onpath[i]) {
				apsp_exc[a][b] = min(apsp_exc[a][b], w);
			}
		}
		
		for (int k=1; k<=n; k++) {
			for (int i=1; i<=n; i++) {
				for (int j=1; j<=n; j++) {
					if (apsp[i][k] + apsp[k][j] < apsp[i][j]) {
						apsp[i][j] = apsp[i][k] + apsp[k][j];
					}
					if (apsp_exc[i][k] + apsp_exc[k][j] < apsp_exc[i][j]) {
						apsp_exc[i][j] = apsp_exc[i][k] + apsp_exc[k][j];
					}
				}
			}
		}
		
		for (int i=0; i<m; i++) {
			int a = eds[i].first.first, b = eds[i].first.second;
			int w = eds[i].second.first;
			if (onpath[i]) {
				distn1[i] = mxh;
				if (path[0] != -1) {
					for (int i=0; i<path.size(); i++) {
						for (int j=i+1; j<path.size(); j++) {
							distn1[i] = min(distn1[i], apsp[n][path[i]] + apsp_exc[path[i]][path[j]] + apsp[path[j]][1]);
						}
					}
				}
			}
			else {
				distn1[i] = wh;
				distn1[i] = min(distn1[i], apsp[n][b] + w + apsp[a][1]);
			}
		}
		
	}
	
	int best = dist1n[m] + distn1[m];
	for (int i=0; i<m; i++) {
		int ix = dist1n[i] + distn1[i] + eds[i].second.second;
		best = min(best, ix);
	}
	if (best >= mxh) cout << -1 << endl;
	else cout << best << endl;
	

}

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

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:129:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |      for (int i=0; i<path.size(); i++) {
      |                    ~^~~~~~~~~~~~
ho_t4.cpp:130:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |       for (int j=i+1; j<path.size(); j++) {
      |                       ~^~~~~~~~~~~~
ho_t4.cpp:185:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 |      for (int i=0; i<path.size(); i++) {
      |                    ~^~~~~~~~~~~~
ho_t4.cpp:186:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |       for (int j=i+1; j<path.size(); j++) {
      |                       ~^~~~~~~~~~~~

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