记录编号	122447	评测结果	AAAAAAAAAA
题目名称	旅行	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.028 s
提交时间	2014-09-23 18:46:52	内存使用	0.37 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <set>
#include <list>
#include <iterator>
#include <ctime>
#include <queue>
#include <stack>
#include <vector>
#include <functional>
#include <deque>
#define For(i,j,k) for(int i=(j);i<=(k);i++)
using namespace std;
typedef long long LL;
typedef unsigned int Uint;
const int INF=0x7fffffff;
const double eps=1e-6;
using namespace std;
//================struct declaration======================

//================var declaration=-========================
const int MAXN=110;
int scc_cnt=0,n,m,k;
stack <int> S;
bool ins[MAXN];
int scc[MAXN],dist[MAXN][MAXN],d[MAXN][20],pre[MAXN],low[MAXN],Index;
//================function declaration====================
void tarjan(int x);
void spfa(int s,int e);
//================main code===============================
int main()
{
  string ProgrammeName="travela";
  string FloderName="COGS";
  freopen((ProgrammeName+".in").c_str(),"r",stdin);
  freopen((ProgrammeName+".out").c_str(),"w",stdout);
#ifdef DEBUG
  clock_t Start_Time=clock();
   system(("cp C:\\Users\\Administrator\\Desktop\\"+FloderName+"\\standard.cpp C:\\Users\\Administrator\\Desktop\\"+FloderName+"\\submit.txt").c_str());
#endif
  while (scanf("%d%d%d",&n,&m,&k)!=EOF)
  {
    if (m==0&&k==0&&n==0)
      break;
    scc_cnt=0;
    memset(scc,0,sizeof(scc));
    memset(dist,-1,sizeof(dist));
    memset(pre,0,sizeof(pre));
    memset(low,0,sizeof(low));
    memset(ins,false,sizeof(ins));
    Index=0;
    For(i,1,m)
    {
      int s,e,t;
      scanf("%d%d%d",&s,&e,&t);
      s++;e++;
      t*=2;
      if (dist[s][e]==-1||dist[s][e]>t)
        dist[s][e]=t;
    } 
    tarjan(1);
    spfa(1,n);
  }
#ifdef DEBUG
  clock_t End_Time=clock();
  printf("\n\nTime Used :%.6lf Ms\n",double(Start_Time-End_Time)/(-CLOCKS_PER_SEC));
#endif
  return 0;
}
//================function code===========================
void tarjan(int x)
{
  pre[x]=low[x]=++Index;
  S.push(x);
  ins[x]=true;
  For(i,1,n)
    if (dist[x][i]!=-1)
    {
      if(pre[i]==0)
      { 
        tarjan(i);
        low[x]=min(low[x],low[i]);
      }
      else if (ins[i])
        low[x]=min(pre[i],low[x]);
    }
  if (pre[x]==low[x])
  {
    scc_cnt++;
    int v=-1;
    do
    {
      v=S.top();
      scc[v]=scc_cnt;
      S.pop();
      ins[v]=false;
    }while (v!=x);
  }
  return ;
}
void spfa(int s,int e)
{
  memset(d,-1,sizeof(d));
  memset(ins,0,sizeof(ins));
  queue <int> Q;
  Q.push(s);
  d[s][0]=0;
  while (!Q.empty())
  {
    int now=Q.front();Q.pop();
    ins[now]=false;
    For(i,1,n)
    {
      if (dist[now][i]==-1) continue;
      int dis;
      if (scc[now]==scc[i])
      {
        dis=dist[now][i]/2;
        For(j,0,k)
          if (d[now][j]!=-1&&(d[i][j]==-1||d[i][j]>d[now][j]+dis))
          {
            d[i][j]=d[now][j]+dis;
            if (!ins[i])
              ins[i]=true,Q.push(i);
          }
      }
      else
      {
        dis=dist[now][i];
        For(j,0,k)
          if (d[now][j]!=-1&&(d[i][j+1]==-1||d[i][j+1]>d[now][j]+dis))
          {
            d[i][j+1]=d[now][j]+dis;
            if (!ins[i])
              ins[i]=true,Q.push(i);
          }
      }
    }
  }
  int ans=-1;
  For(i,0,k)
   if (d[e][i]>0&&(d[e][i]<ans||ans==-1))
     ans=d[e][i];
  printf("%d\n",ans);
}