Submission #5042

#	Time	Username	Problem	Language	Result	Execution time	Memory
5042		cki86201	Ferries (NOI13_ferries)	C++98	40 / 40	252 ms	17428 KiB

ferries

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