Submission #26561

#	Time	Username	Problem	Language	Result	Execution time	Memory
26561		wwiiiii	주유소 (KOI16_gas)	C++14	18 / 100	219 ms	65536 KiB

gas

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

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

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

void dijk(int start)
{
	vector<int> 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 (int i = 1; i <= n; i++) {
		if (d[i] != inf) road[start].push_back({i, d[i] * oil[start]});
	}
}

int ans()
{
	vector<int> d(n + 1, inf);
	priority_queue<edge> pq;
	pq.push({ 1, 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 : road[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] });
			}
		}
	}
	return d[n];
}

int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%d", &oil[i]);
	for (int i = 0; i < m; i++)
	{
		int s, e, c; scanf("%d %d %d", &s, &e, &c);
		graph[s].push_back({ e, c });
		graph[e].push_back({ s, c });
	}
	//1. 다익 n번을 돌려서 각 쌍의 도로 코스트 기준 최단 경로 구하기 => r(A, B)
	for (int i = 1; i <= n; i++) dijk(i);
	//3. c(A, B)를 간선 가중치로 생각하고 다익스트라 한번 더 돌리기
	printf("%d", ans());
}

Compilation message (stderr)

gas.cpp: In function 'int main()':
gas.cpp:71:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
                        ^
gas.cpp:72:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= n; i++) scanf("%d", &oil[i]);
                                                   ^
gas.cpp:75:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int s, e, c; scanf("%d %d %d", &s, &e, &c);
                                             ^

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