Submission #452477

#	Time	Username	Problem	Language	Result	Execution time	Memory
452477		jwvg0425	날다람쥐 (JOI14_ho_t4)	C++17	100 / 100	337 ms	29400 KiB

2014_ho_t4

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second

using namespace std;

template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

vector<ii64> edge[100005];
i64 x;

struct Data
{
	i64 t, fh, h;
	int idx;

	i64 time() const
	{
		return t + llabs(x - fh);
	}

	bool operator<(const Data& r) const
	{
		return time() > r.time();
	}
};

Data dist[100005];

int main()
{
	memset(dist, -1, sizeof(dist));

	int n, m;
	scanf("%d %d %lld", &n, &m, &x);

	vector<i64> h(n + 5);

	for (int i = 1; i <= n; i++)
		scanf("%lld", &h[i]);

	for (int i = 0; i < m; i++)
	{
		int a, b, t;
		scanf("%d %d %d", &a, &b, &t);
		if (h[a] >= t)
			edge[a].emplace_back(b, t);

		if (h[b] >= t)
			edge[b].emplace_back(a, t);
	}

	pq<Data> q;
	dist[1] = { 0, x, x, 1 };
	q.emplace(dist[1]);

	i64 ans = 1ll << 60;

	while (!q.empty())
	{
		auto now = q.top();
		q.pop();

		if (now.idx == n)
			ans = min(ans, dist[n].time() + h[n] - dist[n].h);

		if (now.time() > dist[now.idx].time())
			continue;

		for (auto& e : edge[now.idx])
		{
			Data nxt;
			nxt.t = now.t + e.yy;
			nxt.fh = now.fh;
			nxt.h = now.h - e.yy;
			nxt.idx = e.xx;

			if (nxt.h < 0)
			{
				nxt.fh -= nxt.h;
				nxt.h = 0;
			}

			if (nxt.h > h[e.xx])
			{
				nxt.fh -= h[e.xx] - nxt.h;
				nxt.h = h[e.xx];
			}

			if (dist[e.xx].t != -1 && nxt.time() >= dist[e.xx].time())
				continue;

			dist[e.xx] = nxt;
			q.emplace(nxt);
		}
	}

	if (ans == 1ll << 60)
		ans = -1;

	printf("%lld\n", ans);

	return 0;
}

Compilation message (stderr)

2014_ho_t4.cpp: In function 'int main()':
2014_ho_t4.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |  scanf("%d %d %lld", &n, &m, &x);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
2014_ho_t4.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |   scanf("%lld", &h[i]);
      |   ~~~~~^~~~~~~~~~~~~~~
2014_ho_t4.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |   scanf("%d %d %d", &a, &b, &t);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 50 / 50