oj.uz

답안 #287130

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
287130 2020-08-31T12:22:41 Z reymontada61 Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 165 ms 6700 KB 
#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;
	
 
}

Compilation message

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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 1152 KB Output is correct
2 Correct 34 ms 1024 KB Output is correct
3 Correct 39 ms 1152 KB Output is correct
4 Correct 39 ms 1280 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 34 ms 1024 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 63 ms 1152 KB Output is correct
11 Correct 63 ms 1272 KB Output is correct
12 Incorrect 66 ms 1152 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 6500 KB Output is correct
2 Correct 146 ms 6500 KB Output is correct
3 Correct 158 ms 6700 KB Output is correct
4 Correct 41 ms 1280 KB Output is correct
5 Correct 37 ms 1152 KB Output is correct
6 Correct 37 ms 1144 KB Output is correct
7 Correct 35 ms 1024 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 154 ms 6628 KB Output is correct
10 Correct 165 ms 6504 KB Output is correct
11 Correct 157 ms 6628 KB Output is correct
12 Correct 157 ms 6428 KB Output is correct
13 Incorrect 152 ms 6516 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 1152 KB Output is correct
2 Incorrect 34 ms 1152 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 1152 KB Output is correct
2 Correct 34 ms 1024 KB Output is correct
3 Correct 39 ms 1152 KB Output is correct
4 Correct 39 ms 1280 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 34 ms 1024 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 63 ms 1152 KB Output is correct
11 Correct 63 ms 1272 KB Output is correct
12 Incorrect 66 ms 1152 KB Output isn't correct
13 Halted 0 ms 0 KB -