oj.uz

Submission #5045

# Submission time Handle Problem Language Result Execution time Memory
5045 2014-01-29T10:05:27 Z ainta Ferries (NOI13_ferries) C++
40 / 40
 276 ms 16364 KB 
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
struct A{
	int a, b;
	bool operator <(const A &p)const{
		return b < p.b;
	}
}heap[301000];
vector<int>E[101000], E2[101000];
int n, m, D[101000], top, pv[101000];
int main()
{
	scanf("%d%d", &n, &m);
	int a, b, c, i, x;
	for (i = 0; i < m; i++){
		scanf("%d%d%d", &a, &b, &c);
		E[a].push_back(c);
		E2[b].push_back(a);
	}
	for (i = 1; i <= n; i++){
		if (!E[i].empty())sort(E[i].begin(), E[i].end());
		pv[i] = E[i].size();
		D[i] = 1999999999;
	}
	D[n] = 0;
	heap[top].a = n, heap[top++].b = 0;
	while (1){
		while (top && D[heap[0].a] != -heap[0].b){
			pop_heap(heap, heap + top);
			top--;
		}
		if (!top)break;
		a = heap[0].a, b = D[a];
		pop_heap(heap, heap + top);
		top--;
		for (i = 0; i < E2[a].size(); i++){
			x = E2[a][i];
			--pv[x];
			if (D[x] > b + E[x][pv[x]]){
				D[x] = b + E[x][pv[x]];
				heap[top].a = x, heap[top++].b = -D[x];
				push_heap(heap, heap + top);
			}
		}
	}
	printf("%d\n", D[1]);
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9084 KB Output is correct
2 Correct 4 ms 9084 KB Output is correct
3 Correct 12 ms 9788 KB Output is correct
4 Correct 120 ms 16364 KB Output is correct
5 Correct 124 ms 16364 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9084 KB Output is correct
2 Correct 4 ms 9084 KB Output is correct
3 Correct 8 ms 9744 KB Output is correct
4 Correct 64 ms 12652 KB Output is correct
5 Correct 108 ms 15460 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 9744 KB Output is correct
2 Correct 20 ms 9744 KB Output is correct
3 Correct 236 ms 15816 KB Output is correct
4 Correct 272 ms 15828 KB Output is correct
5 Correct 244 ms 15816 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 15816 KB Output is correct
2 Correct 244 ms 15816 KB Output is correct
3 Correct 276 ms 15816 KB Output is correct
4 Correct 268 ms 15816 KB Output is correct
5 Correct 264 ms 15816 KB Output is correct