QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#199744 | #4479. Slipper | yiyiyi# | AC ✓ | 446ms | 167800kb | C++14 | 1.7kb | 2023-10-04 13:55:28 | 2023-10-04 13:55:28 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
#define re register
#define N 3001200
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
struct edge{
int to,dis,next;
friend bool operator <(edge a,edge b){
return a.dis>b.dis;
}
}e[N<<1];
inline int read(){
int x=0,w=0;char ch=getchar();
while (!isdigit(ch))w|=ch=='-',ch=getchar();
while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
return w?-x:x;
}
priority_queue<edge>q;
int n,m,s,t,dep[N],mxd,vis[N],cnt,dis[N],head[N];
void add(int u,int v,int d){
e[++cnt].to=v;
e[cnt].dis=d;
e[cnt].next=head[u];
head[u]=cnt;
}
void dij(){
for (int i=1;i<=n+mxd*2;++i)vis[i]=0,dis[i]=1e18;
dis[s]=0;
q.push((edge){s,0});
while (!q.empty()){
int u=q.top().to;q.pop();
if(vis[u])continue;
vis[u]=1;
for (int i=head[u];i;i=e[i].next){
int v=e[i].to;
if (dis[v]>dis[u]+e[i].dis){
dis[v]=dis[u]+e[i].dis;
if (!vis[v])q.push((edge){v,dis[v]});
}
}
}
}
void dfs(int u,int fa){
dep[u]=dep[fa]+1;
mxd=max(mxd,dep[u]);
for (int i=head[u];i;i=e[i].next){
int v=e[i].to;
if (v==fa)continue;
dfs(v,u);
}
}
void solve(){
n=read();
cnt=mxd=0;
for (int i=1;i<=n*3;++i)head[i]=dep[i]=0;
for (int i=1;i<n;++i){
int u=read(),v=read(),d=read();
add(u,v,d);add(v,u,d);
}
dfs(1,0);
int k=read(),p=read();
s=read(),t=read();
for (int i=1;i<=n;++i)add(i,dep[i]+n,0);
for (int i=1;i<=n;++i)add(mxd+dep[i]+n,i,p);
for (int i=1;i<=mxd;++i){
if (i-k>0)add(i+n,mxd+i-k+n,0);
if (i+k<=mxd)add(i+n,mxd+i+k+n,0);
}
dij();
printf("%lld\n",dis[t]);
}
signed main(){
int T=read();
while (T--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 446ms
memory: 167800kb
input:
5 121753 103252 40559 325002 32674 51809 946614 18343 12099 625962 27677 48601 114048 11146 12478 906161 121147 77390 208299 39512 95642 154696 90603 43508 378490 4829 7818 191754 73699 31412 536840 106916 89894 374802 113739 90049 411062 113123 73246 740213 38047 120942 903325 51907 41500 822541 90...
output:
114128108 55207815 76620494 17377950755 67601
result:
ok 5 lines