oj.uz

Submission #26561

# Submission time Handle Problem Language Result Execution time Memory
26561 2017-07-03T06:00:35 Z wwiiiii None (KOI16_gas) C++14
18 / 100
 219 ms 65536 KB 
#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

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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2120 KB Output is correct
2 Correct 0 ms 2120 KB Output is correct
3 Correct 0 ms 2120 KB Output is correct
4 Correct 0 ms 2120 KB Output is correct
5 Correct 0 ms 2120 KB Output is correct
6 Correct 0 ms 2120 KB Output is correct
7 Correct 0 ms 2120 KB Output is correct
8 Correct 0 ms 2120 KB Output is correct
9 Correct 0 ms 2120 KB Output is correct
10 Correct 0 ms 2120 KB Output is correct
11 Correct 0 ms 2120 KB Output is correct
12 Correct 0 ms 2120 KB Output is correct
13 Correct 0 ms 2120 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 203 ms 65536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 219 ms 65536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2120 KB Output is correct
2 Correct 0 ms 2120 KB Output is correct
3 Correct 0 ms 2120 KB Output is correct
4 Correct 0 ms 2120 KB Output is correct
5 Correct 0 ms 2120 KB Output is correct
6 Correct 0 ms 2120 KB Output is correct
7 Correct 0 ms 2120 KB Output is correct
8 Correct 0 ms 2120 KB Output is correct
9 Correct 0 ms 2120 KB Output is correct
10 Correct 0 ms 2120 KB Output is correct
11 Correct 0 ms 2120 KB Output is correct
12 Correct 0 ms 2120 KB Output is correct
13 Correct 0 ms 2120 KB Output is correct
14 Incorrect 9 ms 4232 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2120 KB Output is correct
2 Correct 0 ms 2120 KB Output is correct
3 Correct 0 ms 2120 KB Output is correct
4 Correct 0 ms 2120 KB Output is correct
5 Correct 0 ms 2120 KB Output is correct
6 Correct 0 ms 2120 KB Output is correct
7 Correct 0 ms 2120 KB Output is correct
8 Correct 0 ms 2120 KB Output is correct
9 Correct 0 ms 2120 KB Output is correct
10 Correct 0 ms 2120 KB Output is correct
11 Correct 0 ms 2120 KB Output is correct
12 Correct 0 ms 2120 KB Output is correct
13 Correct 0 ms 2120 KB Output is correct
14 Memory limit exceeded 203 ms 65536 KB Memory limit exceeded
15 Halted 0 ms 0 KB -