Submission #5045

#	Time	Username	Problem	Language	Result	Execution time	Memory
5045		ainta	Ferries (NOI13_ferries)	C++98	40 / 40	276 ms	16364 KiB

ferries

#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 / 7
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12