Pagini recente » Cod sursa (job #2184818) | Cod sursa (job #1796484) | Cod sursa (job #1576984) | Cod sursa (job #1548675) | Cod sursa (job #11636)
Cod sursa(job #11636)
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
long best[3202][151],x[1501],y[1501],cost[1501],am[3202][151],
n,m,k,p,i,j,c,max,tt;
int a,b;
int main()
{
freopen("amenzi.in","r",stdin);
freopen("amenzi.out","w",stdout);
scanf("%ld %ld %ld %ld",&n,&m,&k,&p);
for (i=0; i<m; ++i)
{
scanf("%d %d %ld",&x[i],&y[i],&cost[i]);
}
for (i=0;i<k;++i)
{
scanf("%d %d %d",&a,&b,&c);
am[b][a]=c;
}
max=3200;
best[0][1]=1;
for (tt=0;tt<=max;++tt)
{
for (i=1;i<=n;++i)
{
if (best[tt][i]!=0) best[tt][i]+=am[tt][i];
if (best[tt][i]>best[tt+1][i]) best[tt+1][i]=best[tt][i];
}
for (i=0;i<m;++i)
if (tt+cost[i]<=max)
{
if ((best[tt][x[i]]!=0)&&(best[tt][x[i]]>best[tt+cost[i]][y[i]]))
{
best[tt+cost[i]][y[i]]=best[tt][x[i]];
}
if ((best[tt][y[i]]!=0)&&(best[tt][y[i]]>best[tt+cost[i]][x[i]]))
{
best[tt+cost[i]][x[i]]=best[tt][y[i]];
}
}
}
for (i=0;i<p;++i)
{
scanf("%d %d",&a,&b);
printf("%ld\n",best[b][a]-1);
}
fclose(stdin);
fclose(stdout);
return 0;
}