记录编号	39062	评测结果	AAAAAAAAAA
题目名称	旅行	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.044 s
提交时间	2012-07-03 20:25:29	内存使用	0.37 MiB

#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int MAXN=101;
const int MAXM=100001;
const int MAXK=12;
typedef vector<int> Vec;
stack<int> S; 
bool InStack[MAXN];
int times[MAXN][MAXN];
Vec Map[MAXN];
bool walk[MAXN][MAXN];
int dfn[MAXN],low[MAXN];
int flag[MAXK][MAXN];
int dist[MAXK][MAXN];
int Index=0,N,M,K;
 
inline int Min(int a,int b) {return a<b?a:b;}
  
void Tarjan(int u)
{
    dfn[u]=low[u]=++Index;
    S.push(u);
    InStack[u]=1;
    int v;
    for(unsigned int i=0;i<Map[u].size();i++)
    {
        v=Map[u][i];
        if(dfn[v]==0)
        {
            Tarjan(v); low[u]=Min(low[u],low[v]);
        }
        else if(InStack[v]) low[u]=Min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u])
    {
        int Tmp,Top=0,Num[MAXN];
        do
        {
            Tmp=S.top();
            S.pop();
            InStack[Tmp]=0;
            Num[++Top]=Tmp;
        }while(u!=Tmp);
         
        for(int i=1;i<=Top;i++)
        {
            for(int j=1;j<=Top;j++)
            {
                if(i==j) continue;
                if(times[Num[i]][Num[j]]==-1) continue;
                times[Num[i]][Num[j]]/=2;
				walk[Num[i]][Num[j]]=0;
            }
        }
    }
}
 
const int INF=~0u>>2;
 
class QUEUE
{
public:
    int k,u;
};
 
queue<QUEUE> q;
 
inline void SPFA()
{
    for(int i=1;i<=N;i++)
        for(int j=0;j<=K;j++)
            dist[j][i]=INF,
            flag[j][i]=0;
    dist[0][1]=0; flag[0][1]=1;
    q.push((QUEUE){0,1});
     
    int u,v,k,c,nk;
    QUEUE tmp;
    while(q.size())
    {
        tmp=q.front(); q.pop();
        u=tmp.u; k=tmp.k;  flag[k][u]=0;
        if(k==K+1) continue;
        for(unsigned int i=0;i<Map[u].size();i++)
        {
            v=Map[u][i];
            c=dist[k][u]+times[u][v];
			nk=k;
			if(walk[u][v]) nk++;
			if(nk==K+1) continue;
            if(c>=dist[nk][v]) continue;
            dist[nk][v]=c;
            if(flag[nk][v]) continue;
            flag[nk][v]=1;
            q.push((QUEUE){nk,v});
        }
    }
    int ans=INF;
    for(int i=K;i>=0;i--)
        ans=Min(ans,dist[i][N]);
    if(ans==INF) printf("-1\n");
    else printf("%d\n",ans);
}

inline void debug()
{
	for(int i=1;i<=N;i++)
		for(int j=1;j<=N;j++)
			if(times[i][j]!=-1) printf("%d %d %d\n",i,j,times[i][j]);
}

inline void init()
{
	while(scanf("%d %d %d\n",&N,&M,&K)==3)
	{
		if(N==0 && M==0 && K==0) return;
		memset(dfn,0,sizeof(dfn));
		memset(low,0,sizeof(dfn));
		for(int i=1;i<=N;i++) Map[i].clear();
		
		for(int i=1;i<=N;i++)
			for(int j=1;j<=N;j++)
				times[i][j]=-1;
		 
		int u,v,w;
		for(int i=1;i<=M;i++)
		{
			scanf("%d %d %d\n",&u,&v,&w);
			u++,v++;
			walk[u][v]=1;
			if(times[u][v]==-1)
			{
				times[u][v]=2*w;
				Map[u].push_back(v);
				continue;
			}
			if(times[u][v]>2*w)
				times[u][v]=2*w;
		}
		if(N==1)
		{
			printf("0\n");
			continue;
		}
		Tarjan(1);
		//debug();
		SPFA();
	}
}

int main()
{
    freopen("travela.in","r",stdin);
    freopen("travela.out","w",stdout);
    init();
    return 0;
}