```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
int s=0,w=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')w=-1;
c=getchar();
}
while(c>='0'&&c<='9')s=(s<<3)+(s<<1)+(c^48),c=getchar();
return s*w;
}
inline void print(int x)
{
if(x<0)x=-x,putchar('-');
if(x>=10)print(x/10);
putchar(x%10+48);
}
int T,n,m,p,w[1000010];
struct edge
{
int x,res,money;
bool operator<(const edge &a)const
{
if(res==a.res)return money>a.money;
return res<a.res;
}
}f[1000010];
int g[810][810],vis[810];
edge inf={0,-0x3f3f3f3f3f3f3f3f,0x3f3f3f3f3f3f3f3f};
priority_queue<edge> q;
inline void init()
{
for(int i=0;i<=n;i++)f[i]=inf;
memset(vis,0,sizeof(vis));
f[1]={1,0,p};
q.push(f[1]);
}
inline void work()
{
while(q.size())
{
edge now=q.top();
q.pop();
if(vis[now.x])continue;
vis[now.x]=1;
int u=now.x;
//cout<<"u:"<<u<<"\n";
for(int v=1;v<=n;v++)
{
if(g[u][v]==g[1][0]||vis[v])continue;
int Res=now.res,Money=now.money;
if(Money>=g[u][v])
{
Money-=g[u][v];
}
else
{
int xuyao=(g[u][v]-Money+w[u]-1)/w[u];
Res+=xuyao;
Money+=xuyao*w[u];
Money-=g[u][v];
}
edge res={v,Res,Money};
//cout<<"wmhakioi:"<<v<<" "<<Res<<" "<<Money<<"\n";
//cout<<f[v].x<<' '<<f[v].res<<' '<<f[v].money<<" "<<res.x<<" "<<res.res<<" "<<res.money<<"\n";
if(f[v]<res)
{
//puts("DeaphetS");
f[v]=res;
q.push(f[v]);
}
}
}
}
signed main()
{
T=read();
while(T--)
{
n=read();
m=read();
p=read();
memset(g,0x3f,sizeof(g));
for(int i=1;i<=n;i++)
{
w[i]=read();
g[i][i]=0;
}
for(int i=1;i<=m;i++)
{
int u=read(),v=read(),w=read();
g[u][v]=w;
}
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
{
g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
}
}
}
init();
work();
if(f[n].x==0)
{
puts("-1");
continue;
}
print(f[n].res);
puts("");
}
}
```
改了还是不对/kk
by expnoi @ 2023-07-11 20:53:54