Submission #26579

#	Time	Username	Problem	Language	Result	Execution time	Memory
26579		wwiiiii	주유소 (KOI16_gas)	C++14	100 / 100	1008 ms	51900 KiB

gas

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

class edge {
public:
	long long v, c;//vertex, cost
	bool operator<(const edge & next) const {
		if (c != next.c) return c > next.c;
		else return v > next.v;
	}
};

const long long vmax = 2520, emax = 4020, inf = vmax * emax * vmax;
long long n, m;
long long oil[vmax];
vector<edge> graph[vmax];
long long road[vmax][vmax];

void dijk(long long start)
{
	vector<long long> d(n + 1, inf);
	priority_queue<edge> pq;
	pq.push({ start, 0 });
	while (!pq.empty())
	{
		edge now = pq.top(); pq.pop();
		if (now.c > d[now.v]) continue;
		d[now.v] = now.c;
		for (auto next : graph[now.v])
		{
			if (d[next.v] > d[now.v] + next.c)
			{
				d[next.v] = d[now.v] + next.c;
				pq.push({ next.v, d[next.v] });
			}
		}
	}
	for (long long i = 1; i <= n; i++) {
		if (d[i] != inf) road[start][i] = d[i] * oil[start];
	}
}
long long ans()
{
	vector<long long> d(n + 1, inf);
	vector<bool> check(n + 1, false);
	d[1] = 0;
	while (true)
	{
		int mini = 0;
		for (int i = 1; i <= n; i++)
		{
			if (check[i]) continue;
			if (d[mini] > d[i]) mini = i;
		}
		if (mini == 0) break;
		for (int next = 1; next <= n; next++)
		{
			if (d[next] > d[mini] + road[mini][next])
			{
				d[next] = d[mini] + road[mini][next];
			}
		}
		check[mini] = true;
	}
	return d[n];
}

int main()
{
	scanf("%lld %lld", &n, &m);
	for (long long i = 1; i <= n; i++) scanf("%lld", &oil[i]);
	for (long long i = 0; i < m; i++)
	{
		long long s, e, c; scanf("%lld %lld %lld", &s, &e, &c);
		graph[s].push_back({ e, c });
		graph[e].push_back({ s, c });
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			road[i][j] = inf;
	for (long long i = 1; i <= n; i++) dijk(i);
	printf("%lld", ans());
}

Compilation message (stderr)

gas.cpp: In function 'int main()':
gas.cpp:73:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld", &n, &m);
                            ^
gas.cpp:74:59: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (long long i = 1; i <= n; i++) scanf("%lld", &oil[i]);
                                                           ^
gas.cpp:77:57: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   long long s, e, c; scanf("%lld %lld %lld", &s, &e, &c);
                                                         ^

• Subtask 1: 18 / 18
• Subtask 2: 15 / 15
• Subtask 3: 16 / 16
• Subtask 4: 24 / 24
• Subtask 5: 27 / 27