QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#361199#6523. Escape PlanSiilhouetteRE 0ms7192kbC++141.6kb2024-03-22 21:56:512024-03-22 21:56:51

Judging History

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

  • [2024-03-22 21:56:51]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:7192kb
  • [2024-03-22 21:56:51]
  • 提交

answer

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

const int N=100010;
const int M=100010;
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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
3 4 1
3
1 1 1
1 2 1
1 2 2
2 3 1
2 3 2
3 2 2
2 3
2 0 0
1 2 1
1 3 1

output:

4
-1

result:

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

Test #2:

score: -100
Runtime Error

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:


result: