제출 #296814

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
296814		Bruteforceman	Olympic Bus (JOI20_ho_t4)	C++11	37 / 100	1093 ms	163832 KiB

ho_t4

#include "bits/stdc++.h"
using namespace std;
long long d[222][222];
vector <int> g[222], t[222];
int l[50010], r[50010], c[50010], db[50010];
int n, m;
const long long inf = 1e16;

struct data {
	int node;
	long long dist;
	data (int node, long long dist) : node(node), dist(dist) {}
	data () {}
	bool operator < (data d) const {
		return dist > d.dist;
	}
};

vector <long long> shortest_path(int src, int del) {
	priority_queue <data> Q;
	Q.push(data(src, 0));
	vector <long long> dist (n + 1, inf);
	dist[src] = 0;
	while(!Q.empty()) {
		data u = Q.top();
		Q.pop();
		for(auto e : g[u.node]) {
			if(e == del) continue;
			int y = r[e];
			if(u.dist + c[e] < dist[y]) {
				dist[y] = u.dist + c[e];
				Q.push(data(y, dist[y]));
			} 
		} 
	} 
	return dist;
}
vector <int> path(int u, int v) {
	vector <long long> dist (n + 1, inf); 
	dist[u] = 0;
	vector <int> prev (n + 1);
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			if(dist[l[j]] + c[j] < dist[r[j]]) {
				dist[r[j]] = dist[l[j]] + c[j];
				prev[r[j]] = j;
			}
		}
	}
	vector <int> ans;
	if(dist[v] >= inf) return ans;
	while(u != v) {
		ans.push_back(prev[v]);
		v ^= l[prev[v]] ^ r[prev[v]];
	}
	return ans;
} 

bool imp[50010];
vector <long long> delpath[50010], delsrc[50010];

long long delEdge(int u, int x, int e) {
	long long opt = inf;
	for(auto i : t[x]) {
		if(i != e) {
			opt = min(opt, c[i] + d[u][l[i]]);
		}
	}
	return opt;
}

long long solve(int u, int v) {
	long long ans = d[u][v] + d[v][u];
	for(int j = 1; j <= m; j++) {
		long long p1 = delsrc[j][r[j]] + c[j] + db[j] + d[l[j]][v];
		long long p2 = delpath[j][r[j]] + c[j] + d[l[j]][u];
		p2 = min(p2, delpath[j][u]);
		ans = min(ans, p1 + p2);
	}
	return ans;
}
void build() {
	int u = 1, v = n;
	vector <int> can = path(v, u);
	memset(imp, false, sizeof imp);
	for(int i : can) imp[i] = true;
	for(int i = 1; i <= m; i++) {
		if(imp[i]) {
			delpath[i] = shortest_path(v, i);
		} else {
			delpath[i].resize(n + 1);
			for(int j = 1; j <= n; j++) {
				delpath[i][j] = d[v][j];
			}
		}
	} 
	can = path(u, v);
	memset(imp, false, sizeof imp);
	for(int i : can) imp[i] = true;
	for(int i = 1; i <= m; i++) {
		if(imp[i]) {
			delsrc[i] = shortest_path(u, i);
		} else {
			delsrc[i].resize(n + 1);
			for(int j = 1; j <= n; j++) {
				delsrc[i][j] = d[u][j];
			}
		}
	}
}

int main(int argc, char const *argv[])
{
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			if(i != j) {
				d[i][j] = inf;
			}
		}
	}
	for(int i = 1; i <= m; i++) {
		scanf("%d %d %d %d", &l[i], &r[i], &c[i], &db[i]);
		d[l[i]][r[i]] = min(d[l[i]][r[i]], (long long) c[i]);
		g[l[i]].push_back(i);
		t[r[i]].push_back(i);
	}
	for(int k = 1; k <= n; k++) {
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
	build();
	long long ans =  solve(1, n);
	for(int i = 1; i <= m; i++) {
		delsrc[i].swap(delpath[i]);
	}
	ans = min(ans, solve(n, 1));
	if(ans >= inf) ans = -1;
	printf("%lld\n", ans);
	return 0;
}

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

ho_t4.cpp: In function 'int main(int, const char**)':
ho_t4.cpp:114:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  114 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
ho_t4.cpp:123:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  123 |   scanf("%d %d %d %d", &l[i], &r[i], &c[i], &db[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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