主要是建图,建好图之后跑一边dijkstra即可。
一共3N个点,1~N是原图中的点1~N,然后把每层x拆成两个点(N+x)[用于连指向x层的边]和(N+N+x)[用于连从x层指出的边]。
相邻层节点互相可达:AddEdge( N+N+x+1, N+x, C), AddEdge( N+N+x, N+x+1, C);
对于位于x层的节点i,AddEdge(N+x, i, 0), AddEdge(i, N+N+x, 0);
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue> using namespace std; const int MAXN = *;
const int INF = << ; struct HeapNode
{
int d, u;
HeapNode() { }
HeapNode( int _d, int _u ): d(_d), u(_u) { }
bool operator<( const HeapNode& rhs ) const
{
return d > rhs.d;
}
}; struct Edge
{
int from, to, dist;
Edge() { }
Edge( int f, int t, int d ) : from(f), to(t), dist(d) { }
}; struct Dijkstra
{
int n, m;
vector<Edge> edges;
vector<int> G[MAXN];
bool done[MAXN];
int d[MAXN], p[MAXN]; void init( int n )
{
this->n = n;
for ( int i = ; i <= n; ++i ) G[i].clear();
edges.clear();
return;
} void AddEdge( int from, int to, int dist )
{
edges.push_back( Edge( from, to, dist ) );
m = edges.size();
G[from].push_back(m - );
return;
} void dijkstra( int s )
{
priority_queue<HeapNode> Q;
for ( int i = ; i <= n; ++i ) d[i] = INF;
d[s] = ;
memset( done, , sizeof(done) );
Q.push( HeapNode( , s ) );
while ( !Q.empty() )
{
HeapNode x = Q.top();
Q.pop();
int u = x.u;
if ( done[u] ) continue;
done[u] = true;
for ( int i = ; i < (int)G[u].size(); ++i )
{
Edge& e = edges[ G[u][i] ];
if ( d[e.to] > d[u] + e.dist )
{
d[e.to] = d[u] + e.dist;
p[e.to] = G[u][i];
Q.push( HeapNode( d[e.to], e.to ) );
}
}
}
return;
}
}; int N, M, C;
Dijkstra slv;
bool vis[MAXN/]; int main()
{
int T, cas = ;
scanf( "%d", &T );
while ( T-- )
{
scanf( "%d%d%d", &N, &M, &C ); memset( vis, false, sizeof(bool)*(N+) );
slv.init( N* ); for ( int i = ; i <= N; ++i )
{
int layer;
scanf( "%d", &layer );
slv.AddEdge( N + layer, i, );
slv.AddEdge( i, N + N + layer, );
vis[layer] = true;
} for ( int i = ; i < N; ++i )
{
if ( vis[i] && vis[i + ] )
{
slv.AddEdge( N + N + i, N + i + , C );
slv.AddEdge( N + N + i + , N + i, C );
}
} for ( int i = ; i < M; ++i )
{
int u, v, w;
scanf( "%d%d%d", &u, &v, &w );
slv.AddEdge( u, v, w );
slv.AddEdge( v, u, w );
} slv.dijkstra( ); printf( "Case #%d: ", ++cas );
if ( slv.d[N] < INF ) printf( "%d\n", slv.d[N] );
else puts("-1");
}
return ;
}