NK05DSRT - Sa mạc
Tác giả: hieult
Ngôn ngữ: C++
#include <stdio.h>
//#include <conio.h>
long long min(long long a,long long b)
{
if(a<b) return a;
else return b;
}
int main()
{
long long A = 1000000000, B = 1000000;
long long oo = A*B;
//freopen("NK05DSRT.in","r",stdin);
int test,flag[101],n,m,c,x,y,l;
long long a[101][101],d[101];
scanf("%d",&test);
for(int ii = 1;ii<=test;ii++)
{
scanf("%d %d %d",&n,&m,&c);
for(int i = 1;i<=n;i++)
{
d[i] = oo;
flag[i] = 0;
for(int j = 1;j<=n;j++)
a[i][j] = oo;
}
for(int i = 1;i<=m;i++)
{
scanf("%d %d %d",&x,&y,&l);
if(a[x][y]>l)
{
a[x][y] = l;
a[y][x] = l;
}
}
int u = n;flag[n] = 1;d[n]=0;
while(u!=1)
{
for(int i = 1;i<=n;i++)
if(flag[i]==0 && a[i][u] < oo)
{
long long k = oo;
if(a[i][u]>c);
else if(d[u]+a[i][u]<=c)
k = d[u]+a[i][u];
else if(c>2*a[i][u])
{
long long t = (d[u]-c+a[i][u]-1)/(c-2*a[i][u])+1;
k = t*c+d[u]-t*(c-2*a[i][u])+a[i][u];
}
d[i] = min(k,d[i]);
}
long long f = 0,minn = oo;
for(int i = 1;i<=n;i++)
if(flag[i]==0 && d[i]<minn)
{
f = i;
minn = d[i];
}
u = f;
flag[f] = 1;
//for(int i = 1;i<=n;i++)
//printf("%d ",d[i]);
//printf(" ___%d____",u);
//printf("\n");
}
printf("%lld\n",d[1]);
}
//getch();
}