记录编号	39031	评测结果	AAWWWWAWWW
题目名称	旅行	最终得分	30
用户昵称	TBK	是否通过	未通过
代码语言	C++	运行时间	0.110 s
提交时间	2012-07-03 16:37:53	内存使用	76.69 MiB

#include <iostream> 
#include <cmath> 
#include <cstring> 
#include <string> 
#include <cstdio> 
#include <cstdlib> 
#include <iomanip> 
#include <set> 
#include <algorithm> 
#define MAXN 0x7fffffff 
using namespace std; 
int a[100][100][2],b,c,d,l,m=1,m1,m2,m3,n[100],r[100],s,k[100][2],z[100][12],h=1,t,p[10000000][2];
void DFS(int x)
{
    int y;
    r[x]=1;
    k[x][0]=m;
    k[x][1]=m;
    m++;
    n[m3]=x;
    m3++;
    for (y=0;y<b;y++)
    {
        if (a[x][y][0]==0) continue;
        if (k[y][0]==0) 
        {
            DFS(y);
            if (k[y][1]<k[x][1]) k[x][1]=k[y][1];
        }
            else if (r[y]==1) k[x][1]=k[y][0]<k[x][1]?k[y][0]:k[x][1]; 
    }
    if (k[x][0]==k[x][1])
    {
        int i;
        i=n[m3-1];
        while (i!=x)
        {
            r[i]=0;
            m3--;
			a[i][n[m3-1]][1]++;
			a[n[m3-1]][i][1]++;
            i=n[m3-1];
        }
        m3--;
        r[x]=0;
    }
}
void SPFA(void)
{
	bool bo[101][11]={false};
	int i,j;
	while (h>t)
    {
        bo[p[t][0]][p[t][1]]=false;
        for (i=0;i<b;i++)
			for (j=0;j<=d;j++)
				if (p[t][0]!=i)
				{
					if ((a[p[t][0]][i][1]==1)&&(z[p[t][0]][j]<z[i][j]-a[p[t][0]][i][0]))
					{
						if (a[p[t][0]][i][0]!=0) 
						{
							z[i][j]=z[p[t][0]][j]+a[p[t][0]][i][0];
							if (bo[i][j]==false) 
							{
								bo[i][j]=true;
								p[h][0]=i;
								p[h][1]=j;
								h++;
							}
						}
					}
					if ((a[p[t][0]][i][1]==0)&&(z[p[t][0]][j]<z[i][j+1]-a[p[t][0]][i][0]*2))
					{
						if (a[p[t][0]][i][0]!=0)
						{
							z[i][j+1]=z[p[t][0]][j]+a[p[t][0]][i][0]*2;
							if (bo[i][j]==false) 
							{
								bo[i][j]=true;
								p[h][0]=i;
								p[h][1]=j;
								h++;
							}
						}
					}
				}
        t++;
    }
}
int main(void) 
{    
    freopen("travela.in","r",stdin); 
    freopen("travela.out","w",stdout); 
	scanf("%d%d%d",&b,&c,&d);
	while (b!=0||c!=0||d!=0)
	{
		m=1;
		m3=0;
		h=1;
		t=0;
		memset(a,0,sizeof(a));
		memset(r,0,sizeof(r));
		memset(k,0,sizeof(k));
		memset(n,0,sizeof(n));
		if (a[m1][m2][0]==0) a[m1][m2][0]=s;
			else if (s<a[m1][m2][0]) a[m1][m2][0]=s;
		for (l=0;l<c;l++)
		{
			scanf("%d%d",&m1,&m2);
			scanf("%d",&s);
			if (a[m1][m2][0]==0) a[m1][m2][0]=s;
				else if (s<a[m1][m2][0]) a[m1][m2][0]=s;
		}
		for (l=0;l<b;l++)
			if (r[l]==0) DFS(l);
		for (l=0;l<b;l++)
			for (m1=0;m1<=d;m1++)
				z[l][m1]=MAXN;
		z[0][0]=0;
		SPFA();
		s=MAXN;
		for (l=0;l<=d;l++)
			if (z[b-1][l]<s) s=z[b-1][l];
		if (s==MAXN) printf("-1\n");
			else printf("%d\n",s);
		scanf("%d%d%d",&b,&c,&d);
	}
	fclose(stdin); 
    fclose(stdout); 
    return 0; 
}