记录编号	39059	评测结果	AAAAAAAAAA
题目名称	旅行	最终得分	100
用户昵称	CC	是否通过	通过
代码语言	C++	运行时间	0.046 s
提交时间	2012-07-03 19:53:07	内存使用	0.41 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
#define INF 1000000000
struct edge {
    int y,v;
    bool bu;
    edge *next;
    edge (int y,int v,edge *next): y(y),v(v),next(next) {};
}*d[105];
int n,m,K,bcnt,top,Dindex;
int dfn[105],low[105],belong[105],stack[10000],dis[105][20],a[105][105];
bool ins[105],done[10000];
void tarjan(int i) {
    int j;
    dfn[i] = low[i] = ++Dindex;
    ins[i] = 1;
    stack[++top] = i;
    for (edge *p = d[i];p;p = p->next) {
        j = p->y;
        if (!dfn[j]) {
            tarjan(j);
            if (low[j] < low[i]) 
                low[i] = low[j];
        }
        else if (ins[j] && dfn[j] < low[i])
            low[i] = dfn[j];
    }
    if (dfn[i] == low[i]) {
        bcnt++;
        do {
            j = stack[top--];
            ins[j] = 0;
            belong[j] = bcnt;
        } while (j != i);
    }
}
void spfa() {
    int q[1000000];
    bool inq[20000];
    int head = 0,tail = 0;
    dis[0][0] = 0;
    while (head <= tail) {
        int now = q[head++];
        for (edge *p = d[now];p;p = p->next) 
		  for (int k = 0;k <= K;k++) 
			if (dis[now][k] != -1 && (dis[p->y][k + p->bu] == -1 || dis[p->y][k + p->bu] > dis[now][k] + p->v)) {
			    dis[p->y][k + p->bu] = dis[now][k] + p->v;
			    if (!inq[p->y]) 
				  inq[q[++tail] = p->y] = 1;
			}
        inq[now] = 0;
    }
}
 
int main() {
    freopen("travela.in","r",stdin);
    freopen("travela.out","w",stdout);
    scanf("%d%d%d\n", &n, &m, &K);
    while (n != 0 && m != 0 && K != 0) {
        int p,q,r; 
        for (int i = 0;i < n;i++)
            for (int j = 0;j < n;j++) a[i][j] = INF;
        for (int i = 1;i <= m;i++) {
            scanf("%d%d%d", &p, &q, &r);
            if (a[p][q] > r) a[p][q] = r;
        }
        memset(d,0,sizeof(d));
        for (int i = 0;i < n;i++) 
            for (int j = 0;j < n;j++) 
                if (a[i][j] != INF) d[i] = new edge(j,a[i][j],d[i]);
        bcnt = top = Dindex = 0;
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        for (int i = 0;i < n;i++) 
            if (!dfn[i]) 
                tarjan(i);
        for (int i = 0;i < n;i++) 
            for (edge *p = d[i];p;p = p->next) if (belong[p->y] != belong[i]) {
                p->v *= 2;
                p->bu = 1;
            }
        memset(dis,-1,sizeof(dis));
        spfa();
        n--;
        int ans = INF;
        for (int i = 0;i <= K;i++)
            if (dis[n][i] != -1 && dis[n][i] < ans) ans = dis[n][i];
        if (ans == INF) ans = -1;
        printf("%d\n", ans);
        scanf("%d%d%d", &n, &m, &K);
    }
    return 0;
}