oj.uz

Submission #5042

# Submission time Handle Problem Language Result Execution time Memory
5042 2014-01-29T08:08:26 Z cki86201 Ferries (NOI13_ferries) C++
40 / 40
 252 ms 17428 KB 
#include<stdio.h>
#include<queue>
using namespace std;

typedef pair<int,int> Pi;
#define X first
#define Y second

priority_queue <int> edge[100010];
priority_queue <Pi, vector<Pi>, greater<Pi> >pq;
int st[100010], en[600060], nxt[600060], len[600060];
void add(int s,int e,int l,int c){nxt[c]=st[s],st[s]=c,en[c]=e,len[c]=l;}
int dis[100010];
bool chk[100010];

int main()
{
	int n, m;
	scanf("%d%d",&n,&m);
	int i;
	for(i=1;i<=m;i++){
		int x, y, z;
		scanf("%d%d%d",&x,&y,&z);
		add(y,x,z,i);
		edge[x].push(z);
	}
	pq.push(Pi(0,n));
	while(!pq.empty()){
		Pi tmp = pq.top();
		pq.pop();
		if(chk[tmp.Y])continue;
		chk[tmp.Y] = 1;
		dis[tmp.Y] = tmp.X;
		for(i=st[tmp.Y];i;i=nxt[i]){
			if(chk[en[i]])continue;
			pq.push(Pi(edge[en[i]].top() + tmp.X, en[i]));
			edge[en[i]].pop();
		}
	}
	printf("%d",dis[1]);
	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12248 KB Output is correct
2 Correct 0 ms 12248 KB Output is correct
3 Correct 12 ms 12784 KB Output is correct
4 Correct 132 ms 17428 KB Output is correct
5 Correct 136 ms 17428 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12248 KB Output is correct
2 Correct 0 ms 12248 KB Output is correct
3 Correct 12 ms 12784 KB Output is correct
4 Correct 64 ms 14844 KB Output is correct
5 Correct 96 ms 15564 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12512 KB Output is correct
2 Correct 16 ms 12512 KB Output is correct
3 Correct 204 ms 15548 KB Output is correct
4 Correct 252 ms 16064 KB Output is correct
5 Correct 248 ms 16052 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 15680 KB Output is correct
2 Correct 208 ms 15548 KB Output is correct
3 Correct 252 ms 16444 KB Output is correct
4 Correct 240 ms 16432 KB Output is correct
5 Correct 252 ms 16444 KB Output is correct