QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#361199 | #6523. Escape Plan | Siilhouette | RE | 0ms | 7192kb | C++14 | 1.6kb | 2024-03-22 21:56:51 | 2024-03-22 21:56:51 |
Judging History
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...