先求任意两点之间不经过城堡的最短路。d[i][j]表示到达i点使用了j次鞋子的最短路长度。
以下是我的代码：
#include <queue>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int kMaxn = 107;
const int kMaxm = kMaxn * kMaxn;
const int kInf = 0x7f7f7f7f;
int A, B, M, L, K, g[kMaxn][kMaxn];
int d[kMaxn][17];
bool inq[kMaxn][17];
struct State {
State ( const int &_u, const int &_k ) : u ( _u ), k ( _k ) { }
int u, k;
};
void Input () {
memset ( g, 0x7f, sizeof ( g ) );
scanf ( "%d%d%d%d%d", &A, &B, &M, &L, &K );
while ( M-- ) {
int u, v, w;
scanf ( "%d%d%d", &u, &v, &w );
g[u][v] = g[v][u] = w;
}
}
void Solve () {
for ( int k = 1; k <= A; k++ )
for ( int i = 1; i <= A+B; i++ )
for ( int j = 1; j <= A+B; j++ )
if ( g[i][k] < kInf && g[k][j] < kInf && g[i][j] > g[i][k] + g[k][j] )
g[i][j] = g[i][k] + g[k][j];
queue<State> q;
memset ( d, 0x7f, sizeof ( d ) );
memset ( inq, false, sizeof ( inq ) );
d[A+B][0] = 0;
q.push ( State ( A+B, 0 ) );
while ( !q.empty() ) {
int u = q.front().u, k = q.front().k;
q.pop(); inq[u][k] = false;
for ( int v = 1; v <= A + B; v++ ) {
if ( k < K && g[u][v] <= L ) {
if ( d[v][k+1] > d[u][k] ) {
d[v][k+1] = d[u][k];
if ( !inq[v][k+1] ) {
q.push ( State ( v, k+1 ) );
inq[v][k+1] = true;
}
}
if ( d[v][k] > d[u][k] + g[u][v] ) {
d[v][k] = d[u][k] + g[u][v];
if ( !inq[v][k] ) {
q.push ( State ( v, k ) );
inq[v][k] = true;
}
}
}
else {
if ( d[v][k] > d[u][k] + g[u][v] ) {
d[v][k] = d[u][k] + g[u][v];
if ( !inq[v][k] ) {
q.push ( State ( v, k ) );
inq[v][k] = true;
}
}
}
}
}
int ans = kInf;
for ( int i = 0; i <= K; i++ )
ans = min ( ans, d[1][i] );
printf ( "%d\n", ans );
}
int main () {
#ifndef ONLINE_JUDGE
freopen ( "data.in", "r", stdin );
#endif
int T;
scanf ( "%d", &T );
while ( T-- ) {
Input ();
Solve ();
}
return 0;
}
posted on 2011-11-04 09:25
lee1r 阅读(944)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：图论