QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#361202	#6523. Escape Plan	Siilhouette	WA	454ms	68852kb	C++14	1.6kb	2024-03-22 21:59:13	2024-03-22 21:59:13

Judging History

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

[2024-03-22 21:59:13]
评测

测评结果：WA
用时：454ms
内存：68852kb

查看

[2024-03-22 21:59:13]
提交

answer

#define _CRT_SECURE_NO_WARNINGS
#include<queue>
#include<cmath>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=1000010;
const int M=1000010;
typedef long long ll;
int n,m,K,tim,valid[N],d[N];

struct Graph{
	int tot,head[N],suiv[M<<1],edge[M<<1],ver[M<<1];
	bool vis[N<<1];
	ll dis[N<<1];
	priority_queue<pair<ll,int> >q;

	inline void init()
	{
		for(int i=0;i<=tot;i++)
			head[i]=dis[i]=vis[N]=0;
		while(q.size())q.pop();
		tot=0;
	}

	inline void lnk(int x,int y,int z)
	{
		ver[++tot]=y;
		edge[tot]=z;
		suiv[tot]=head[x];
		head[x]=tot;
	}

	inline void dijkstra()
	{
		while(q.size())
		{
		
			int x=q.top().second;ll _d=q.top().first;q.pop();
			if(!(valid[x]==tim||!--d[x]))continue;
		//	cout<<"x "<<x<<endl;
			
			dis[x]=-_d;
		//	cout<<dis[x]<<endl;
			vis[x]=1;
			for(int i=head[x];i;i=suiv[i])
			{
				int y=ver[i],z=edge[i];
				if(vis[y])continue;
				q.push(make_pair(-(dis[x]+z),y));
		//		cout<<"q push" <<-(dis[x]+z)<<" "<<y<<endl;
			}
		}
	}

}e;

int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		tim++;
		e.init();
		scanf("%d%d%d",&n,&m,&K);
		memset(e.dis,0x3f,sizeof(e.dis));
		ll inf=e.dis[0];
		for(int i=1,pos;i<=K;i++)
		{
			scanf("%d",&pos),e.q.push(make_pair(0,pos));
			valid[pos]=tim;
			e.dis[pos]=0;
		}
		for(int i=1;i<=n;i++)
			scanf("%d",&d[i]),d[i]++;
		for(int i=1,x,y,z;i<=m;i++)
			scanf("%d%d%d",&x,&y,&z),e.lnk(x,y,z),e.lnk(y,x,z);
		e.dijkstra();
		printf("%lld\n",e.dis[1]==inf?-1:e.dis[1]);
	}
	return 0;
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 6ms

memory: 30424kb

input:

output:

4
-1

result:

ok 2 number(s): "4 -1"

Test #2:

score: -100

Wrong Answer

time: 454ms

memory: 68852kb

input:

100
100 1808 2
94 47
3 3 0 2 4 3 3 4 0 0 2 2 2 3 2 4 0 2 3 4 4 2 0 3 4 3 1 0 2 1 2 2 0 3 4 4 4 1 2 2 3 1 0 0 3 1 4 2 1 3 3 4 3 0 4 1 0 3 2 1 4 4 1 3 2 3 3 3 3 1 0 3 0 4 3 1 0 4 0 4 4 1 2 0 0 4 1 3 3 3 0 2 2 1 1 2 3 4 1 2
72 29 1138
59 78 2398
95 5 1610
32 46 4176
36 99 8143
100 69 413
61 58 1595
9 9...

output:

5109
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1

result:

wrong answer 2nd numbers differ - expected: '1021', found: '-1'