제출 #224114

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

ho_t4

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
#define F first
#define S second
using namespace std;
typedef pair<int, int> ii;
typedef pair<long long, long long> ll;
typedef pair<long long, ii> yay;
typedef pair<ii, ll> edge;
const long long INF = 1000000000000000000;
int main() {
	int N, M;
	scanf("%d %d", &N, &M);
	edge edges[M];
	bool inr[M], inb[M], inrr[M], inrb[M];
	fill_n(inr, M, 0);
	fill_n(inb, M, 0);
	fill_n(inrr, M, 0);
	fill_n(inrb, M, 0);
	vector<int> adjlist[N], revlist[N];
	for (int i = 0; i < M; ++i) {
		scanf("%d %d %lld %lld", &edges[i].F.F, &edges[i].F.S, &edges[i].S.F, &edges[i].S.S);
		--edges[i].F.F, --edges[i].F.S;
		adjlist[edges[i].F.F].push_back(i);
		revlist[edges[i].F.S].push_back(i);
	}
	long long rsp[N], bsp[N], rrsp[N], rbsp[N];
	fill_n(rsp, N, INF);
	priority_queue< yay, vector<yay>, greater<yay> > dijkstra;
	dijkstra.push(yay(0, ii(0, -1)));
	rsp[0] = 0;
	while (!dijkstra.empty()) {
		yay a = dijkstra.top();
		dijkstra.pop();
		if (a.F > rsp[a.S.F]) continue;
		if (a.S.S != -1) inr[a.S.S] = true;
		for (int j: adjlist[a.S.F]) {
			if (edges[j].S.F + a.F < rsp[edges[j].F.S]) {
				rsp[edges[j].F.S] = edges[j].S.F + a.first;
				dijkstra.push(yay(rsp[edges[j].F.S], ii(edges[j].F.S, j)));
			}
		}
	}
	fill_n(bsp, N, INF);
	dijkstra.push(yay(0, ii(N - 1, -1)));
	bsp[N - 1] = 0;
	while (!dijkstra.empty()) {
		yay a = dijkstra.top();
		dijkstra.pop();
		if (a.F > bsp[a.S.F]) continue;
		if (a.S.S != -1) inb[a.S.S] = true;
		for (int j: adjlist[a.S.F]) {
			if (edges[j].S.F + a.F < bsp[edges[j].F.S]) {
				bsp[edges[j].F.S] = edges[j].S.F + a.first;
				dijkstra.push(yay(bsp[edges[j].F.S], ii(edges[j].F.S, j)));
			}
		}
	}
	fill_n(rrsp, N, INF);
	dijkstra.push(yay(0, ii(0, -1)));
	rrsp[0] = 0;
	while (!dijkstra.empty()) {
		yay a = dijkstra.top();
		dijkstra.pop();
		if (a.F > rrsp[a.S.F]) continue;
		if (a.S.S != -1) inrr[a.S.S] = true;
		for (int j: revlist[a.S.F]) {
			if (edges[j].S.F + a.F < rrsp[edges[j].F.F]) {
				rrsp[edges[j].F.F] = edges[j].S.F + a.first;
				dijkstra.push(yay(rrsp[edges[j].F.F], ii(edges[j].F.F, j)));
			}
		}
	}
	fill_n(rbsp, N, INF);
	dijkstra.push(yay(0, ii(N - 1, -1)));
	rbsp[N - 1] = 0;
	while (!dijkstra.empty()) {
		yay a = dijkstra.top();
		dijkstra.pop();
		if (a.F > rbsp[a.S.F]) continue;
		if (a.S.S != -1) inrb[a.S.S] = true;
		for (int j: revlist[a.S.F]) {
			if (edges[j].S.F + a.F < rbsp[edges[j].F.F]) {
				rbsp[edges[j].F.F] = edges[j].S.F + a.first;
				dijkstra.push(yay(rbsp[edges[j].F.F], ii(edges[j].F.F, j)));
			}
		}
	}
	long long ans = rsp[N - 1] + bsp[0];
	for (int i = 0; i < M; ++i) {
		long long a, b, c = edges[i].S.F, d = edges[i].S.F;
		if (inr[i]) {
			long long rsp[N];
			fill_n(rsp, N, INF);
			dijkstra.push(yay(0, ii(0, -1)));
			rsp[0] = 0;
			while (!dijkstra.empty()) {
				yay a = dijkstra.top();
				dijkstra.pop();
				if (a.F > rsp[a.S.F]) continue;
				for (int j: adjlist[a.S.F]) {
					if (j == i) continue;
					if (edges[j].S.F + a.F < rsp[edges[j].F.S]) {
						rsp[edges[j].F.S] = edges[j].S.F + a.first;
						dijkstra.push(yay(rsp[edges[j].F.S], ii(edges[j].F.S, j)));
					}
				}
				if (a.S.F == edges[i].F.S) {
					if (edges[i].S.F + a.F < rsp[edges[i].F.F]) {
						rsp[edges[i].F.F] = edges[i].S.F + a.first;
						dijkstra.push(yay(rsp[edges[i].F.F], ii(edges[i].F.F, i)));
					}
				}
			}
			a = rsp[N - 1], c += rsp[edges[i].F.S];
		} else a = rsp[N - 1], c += rsp[edges[i].F.S];
		if (inb[i]) {
			long long bsp[N];
			fill_n(bsp, N, INF);
			dijkstra.push(yay(0, ii(N - 1, -1)));
			bsp[N - 1] = 0;
			while (!dijkstra.empty()) {
				yay a = dijkstra.top();
				dijkstra.pop();
				if (a.F > bsp[a.S.F]) continue;
				for (int j: adjlist[a.S.F]) {
					if (j == i) continue;
					if (edges[j].S.F + a.F < bsp[edges[j].F.S]) {
						bsp[edges[j].F.S] = edges[j].S.F + a.first;
						dijkstra.push(yay(bsp[edges[j].F.S], ii(edges[j].F.S, j)));
					}
				}
				if (a.S.F == edges[i].F.S) {
					if (edges[i].S.F + a.F < bsp[edges[i].F.F]) {
						bsp[edges[i].F.F] = edges[i].S.F + a.first;
						dijkstra.push(yay(bsp[edges[i].F.F], ii(edges[i].F.F, i)));
					}
				}
			}
			b = bsp[0], d += bsp[edges[i].F.S];
		} else b = bsp[0], d += bsp[edges[i].F.S];
		if (inrr[i]) {
			long long rrsp[N];
			fill_n(rrsp, N, INF);
			dijkstra.push(yay(0, ii(0, -1)));
			rrsp[0] = 0;
			while (!dijkstra.empty()) {
				yay a = dijkstra.top();
				dijkstra.pop();
				if (a.F > rrsp[a.S.F]) continue;
				for (int j: revlist[a.S.F]) {
					if (j == i) continue;
					if (edges[j].S.F + a.F < rrsp[edges[j].F.F]) {
						rrsp[edges[j].F.F] = edges[j].S.F + a.first;
						dijkstra.push(yay(rrsp[edges[j].F.F], ii(edges[j].F.F, j)));
					}
				}
				if (a.S.F == edges[i].F.F) {
					if (edges[i].S.F + a.F < rrsp[edges[i].F.S]) {
						rrsp[edges[i].F.S] = edges[i].S.F + a.first;
						dijkstra.push(yay(rrsp[edges[i].F.S], ii(edges[i].F.S, i)));
					}
				}
			}
			d += rrsp[edges[i].F.F];
		} else d += rrsp[edges[i].F.F];
		if (inrb[i]) {
			long long rbsp[N];
			fill_n(rbsp, N, INF);
			dijkstra.push(yay(0, ii(N - 1, -1)));
			rbsp[N - 1] = 0;
			while (!dijkstra.empty()) {
				yay a = dijkstra.top();
				dijkstra.pop();
				if (a.F > rbsp[a.S.F]) continue;
				for (int j: revlist[a.S.F]) {
					if (j == i) continue;
					if (edges[j].S.F + a.F < rbsp[edges[j].F.F]) {
						rbsp[edges[j].F.F] = edges[j].S.F + a.first;
						dijkstra.push(yay(rbsp[edges[j].F.F], ii(edges[j].F.F, j)));
					}
				}
				if (a.S.F == edges[i].F.F) {
					if (edges[i].S.F + a.F < rbsp[edges[i].F.S]) {
						rbsp[edges[i].F.S] = edges[i].S.F + a.first;
						dijkstra.push(yay(rbsp[edges[i].F.S], ii(edges[i].F.S, i)));
					}
				}
			}
			c += rbsp[edges[i].F.F];
		} else c += rbsp[edges[i].F.F];
		ans = min(ans, min(a, c) + min(b, d) + edges[i].S.S);
	}
	printf("%lld", ans < INF ? ans : -1);
	return 0;
}

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

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~~
ho_t4.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %lld %lld", &edges[i].F.F, &edges[i].F.S, &edges[i].S.F, &edges[i].S.S);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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