校賽題,比賽的時(shí)候沒(méi)有仔細(xì)想，現(xiàn)在回想就是一個(gè)二維最短路，貌似和上次09年月賽俊神出的那道trip解法類似。。。
#include <stdio.h>
#include <string.h>
#define N 105
const long long INF = 1LL << 60;
long long g[N][N], dis[11][N];
bool mark[11][N];
void Pre()
{
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
{
g[i][j] = INF;
}
for(int j = 0; j < 11; j++)
{
dis[j][i] = INF;
}
}
}
long long Dijkstra(int st, int ed, int x, int n)
{
memset(mark, 0, sizeof(mark));
dis[0][st] = 0;
for(int i = 0; i < x * n; i++)
{
long long mmin = INF;
int u = -1, cur, next;
for(int j = 0; j < n; j++)
{
for(int k = 0; k < x; k++)
{
if(!mark[k][j] && dis[k][j] < mmin)
{
mmin = dis[k][j];
u = j;
cur = k;
next = (k + 1) % x;
}
}
}
if(-1 == u) return -1;
//printf("u = %d, cur = %d\n", u, cur);
mark[cur][u] = 1;
if(mark[0][ed]) return dis[0][ed];
for(int j = 0; j < n; j++)
{
if(!mark[next][j] && dis[cur][u] + g[u][j] < dis[next][j])
{
dis[next][j] = dis[cur][u] + g[u][j];
//printf("next = %d, j = %d\n", next, j);
}
}
}
}
int main()
{
int t, n, m, st, ed, x;
scanf("%d", &t);
while(t--)
{
Pre();
scanf("%d %d", &n, &m);
for(int i = 0; i < m; i++)
{
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
if(c < g[a][b]) g[a][b] = c;
}
scanf("%d %d %d", &st, &ed, &x);
long long ans = Dijkstra(st, ed, x, n);
if(-1 == ans) printf("No Answer!\n");
else printf("%I64d\n", ans);
}
return 0;
}