QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#88242#5506. HyperloopmeaningfulRE 539ms18736kbC++142.3kb2023-03-15 18:29:162023-03-15 18:29:20

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-15 18:29:20]
  • 评测
  • 测评结果:RE
  • 用时:539ms
  • 内存:18736kb
  • [2023-03-15 18:29:16]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define ust int
#define fi first
#define sc second
using namespace std;
pair<ust,ust> M[6000000];
int cnt;
ust dis[100002];
int lst[100002],n,bg[100002],ed[100002];
ust lstl[100002];
int fir[100002],to[600002],nxt[600002],TOT;ust w[600002];
void add(int u,int v,ust ww)
{
	TOT++;nxt[TOT]=fir[u];fir[u]=TOT,to[TOT]=v;w[TOT]=ww;
	swap(u,v);
	TOT++;nxt[TOT]=fir[u];fir[u]=TOT,to[TOT]=v;w[TOT]=ww;
}
pair<ust,ust> T[2][100002];int tot[2];
void gt(int tg,int x,ust o)
{
	tot[tg]=0;
	for (int i=bg[x];i<ed[x];i++) if (M[i].fi>o)
	{
		T[tg][tot[tg]++]=M[i];
	}
	else if (M[i].fi==o)
	{
		T[tg][tot[tg]]=M[i];T[tg][tot[tg]++].sc++;
	}else
	{
		if (tot[tg]==0 || T[tg][tot[tg]-1].fi>o)
		{
			T[tg][tot[tg]++]={o,1};
		}
		T[tg][tot[tg]++]=M[i];
	}
	if (tot[tg]==0 || T[tg][tot[tg]-1].fi>o)
	{
		T[tg][tot[tg]++]={o,1};
	}
	//cout<<x<<' '<<o<<':'<<endl;
	//for (int i=0;i<tot[tg];i++) cout<<T[tg][i].fi<<' '<<T[tg][i].sc<<endl;
}
int chk(int x,int y,int z,ust ox,ust oy)
{
	gt(0,x,ox);
	gt(1,y,oy);
	int i;
	for (i=0;i<tot[0] && i<tot[1];i++)
	{
		if (T[0][i]!=T[1][i])
		{
			if (T[0][i]<T[1][i]) return 1;
			else return 0;
		}
	}
	return 0;
}
void dij()
{
	for (int i=0;i<=n;i++) dis[i]=65000,lst[i]=0;
	cnt=0;dis[1]=0;
	priority_queue<pair<int,int> >pq;
	pq.push({0,1});
	lst[1]=-1;
	while (!pq.empty())
	{
		int x=pq.top().second;pq.pop();
		if (x==n) break;
		bg[x]=cnt;
		gt(0,lst[x],lstl[x]);
		for (int i=0;i<tot[0];i++) M[cnt++]=T[0][i];
		ed[x]=cnt;
		for (int i=fir[x];i;i=nxt[i]) if (!lst[to[i]] || (int)dis[to[i]]>(int)dis[x]+w[i])
		{
			dis[to[i]]=dis[x]+w[i];
			lst[to[i]]=x;lstl[to[i]]=w[i];
			pq.push({-1.0*dis[to[i]],to[i]});
		}
		else if (lst[to[i]] && (int)dis[to[i]]==(int)dis[x]+w[i])
		{
			if (chk(lst[to[i]],x,to[i],lstl[to[i]],w[i])) lst[to[i]]=x,lstl[to[i]]=w[i];
		}
	}
	vector<int> ans;
	int nw=n;
	while (nw!=-1) ans.push_back(nw),nw=lst[nw];
	reverse(ans.begin(),ans.end());
	cout<<ans.size()<<endl;
	for (auto p:ans) cout<<p<<' ';cout<<endl;
}
int main()
{
	int TT;cin>>TT;
	while (TT--)
	{
		int m,i;cin>>n>>m;cnt=0;TOT=0;
		for (i=1;i<=n;i++) fir[i]=0;
		for (i=1;i<=m;i++)
		{
			int u,v;cin>>u>>v;
			ust ww;cin>>ww;
			add(u,v,ww);
		}
		dij();
	}
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 5348kb

input:

2
4 6
1 2 1
1 3 2
2 3 1
2 4 2
3 4 1
1 4 4
6 11
1 2 9
2 3 12
3 4 3
4 5 5
5 6 10
6 1 22
2 4 9
3 6 1
4 6 5
2 5 2
3 5 8

output:

3
1 2 4 
5
1 2 5 3 6 

result:

ok correct (2 test cases)

Test #2:

score: 0
Accepted
time: 493ms
memory: 5528kb

input:

600
320 1547
204 81 13768
232 97 9939
97 249 3719
201 109 14322
183 132 40881
142 143 1
275 186 24548
18 236 7907
30 317 11845
131 130 1
311 300 11704
141 92 41925
174 191 32128
119 120 1
184 183 1
310 309 1
283 270 25477
233 141 36076
212 92 13770
307 110 40656
218 137 14033
180 85 41892
200 199 44...

output:

184
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 10...

result:

ok correct (600 test cases)

Test #3:

score: 0
Accepted
time: 539ms
memory: 18736kb

input:

4
100000 220000
48940 43355 42347
77914 77913 1
45236 82683 42904
22563 16038 34866
81537 81538 43088
49803 51485 25497
63071 25523 14336
44102 39850 43782
13607 92386 16724
98711 73651 46840
17775 16801 28765
5757 98829 13508
85095 48444 1
9198 43003 32678
14461 14462 1
20245 48742 18138
89120 8911...

output:

35000
1 24721 99899 75483 98325 75489 73433 99907 61946 61953 99423 25093 25110 25111 25096 43056 43055 43054 43053 43052 43051 43050 43049 43048 43047 43046 43045 43044 43043 43042 43041 43040 43039 43038 43037 43036 43035 43034 43033 43032 43031 43030 43029 43028 43027 43026 43025 43024 43023 4302...

result:

ok correct (4 test cases)

Test #4:

score: -100
Runtime Error

input:

4
100000 160000
5533 94547 28459
14992 20984 20548
70133 92512 27510
9013 9012 304
13621 40571 47787
305 306 262
6987 6988 135
16234 16992 40656
26246 49196 27701
19103 60272 44055
91532 91531 38290
70778 68341 35147
32524 32523 13
85786 50300 40970
49277 29735 13942
43446 34519 42455
77623 17031 34...

output:


result: