#include <cstdio>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
#define MAXN 1010
typedef pair<int,int> PAIR;
int n, m, s, t, k;
vector< PAIR > map[MAXN], graph[MAXN];
int h[MAXN];
struct Node
{
int v, cost;
Node() {}
Node( int a, int b ):v(a), cost(b) {}
};
bool operator< ( Node a, Node b )
{
return a.cost+ h[a.v]> b.cost+ h[b.v];
}
void dijk()
{
fill( h, h+ n+ 1, INT_MAX );
priority_queue< PAIR > q;
q.push( make_pair( t, 0 ) );
h[t]= 0;
while( !q.empty() )
{
int u= q.top().first, len= q.top().second; q.pop();
if( h[u]!= len ) continue;
for( size_t i= 0; i< graph[u].size(); ++i )
{
int v= graph[u][i].first, cost= graph[u][i].second;
if( h[v]> len+ cost )
{
q.push( make_pair( v, len+ cost ) );
h[v]= len+ cost;
}
}
}
}
int A_star()
{
priority_queue< Node > q;
int c[MAXN];
fill( c, c+ n+ 1, 0 );
if( h[s]== INT_MAX ) return -1;
q.push( Node( s, 0 ) );
while( !q.empty() )
{
int v= q.top().v, cost= q.top().cost; q.pop();
c[v]++;
if( c[t]== k ) return cost;
if( c[v]> k ) continue;
for( size_t i= 0; i< map[v].size(); ++i )
q.push( Node( map[v][i].first, cost+ map[v][i].second ) );
}
return -1;
}
int main()
{
scanf("%d%d",&n,&m );
for( int i= 0; i< m; ++i )
{
int u, v, d;
scanf("%d%d%d",&u,&v,&d );
map[u].push_back ( make_pair( v, d ) );
graph[v].push_back ( make_pair( u, d ) );
}
scanf("%d%d%d",&s,&t,&k );
if( s== t ) k++;
dijk();
printf("%d\n",A_star() );
return 0;
}
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
#define N 1002
#define inf 1<<30
typedef pair<int,int> PAIR;
int n, m, S, T, K;
vector<PAIR> g1[N], g2[N];
int h[N], cnt[N];
void dijk(){
priority_queue<PAIR,vector<PAIR>,greater<PAIR> > q;
for( int i= 0; i<= n; ++i ) h[i]= inf;
h[T]= 0; q.push( PAIR(0,T) );
while( !q.empty() ){
int u= q.top().second, w= q.top().first; q.pop();
if( w!= h[u] ) continue;
for( size_t i= 0; i< g2[u].size(); ++i ){
int v= g2[u][i].first, d= g2[u][i].second;
if( h[u]+ d< h[v] ){
h[v]= h[u]+ d;
q.push( PAIR( h[v], v ) );
}
}
}
}
struct cmp{
inline bool operator()( PAIR const& a, PAIR const& b ){
return a.second+ h[a.first]> b.second+ h[b.first];
}
};
int A_star(){
if( h[S]== inf ) return -1;
priority_queue<PAIR,vector<PAIR>,cmp> q;
q.push( PAIR( S, 0 ) );
while( !q.empty() ){
int u= q.top().first, w= q.top().second; q.pop();
cnt[u]++;
if( cnt[T]== K ) return w;
if( cnt[u]> K ) continue;
for( size_t i= 0; i< g1[u].size(); ++i )
q.push( PAIR( g1[u][i].first, g1[u][i].second+ w ) );
}
return -1;
}
inline int read(){
char ch;
int d;
while( ch= getchar(), ch< '0' || ch> '9' );
d= ch- '0';
while( ch= getchar(), ch>= '0' && ch<= '9' )
d= d* 10+ ch- '0';
return d;
}
int main(){
scanf("%d%d",&n,&m );
int u, v, d;
while( m-- ){
u= read(); v= read(); d= read();
g1[u].push_back( PAIR(v,d) );
g2[v].push_back( PAIR(u,d) );
}
scanf("%d%d%d",&S,&T,&K );
if( S== T ) K++;
dijk();
printf("%d\n", A_star() );
return 0;
}
posted on 2008-12-04 14:00
Darren 阅读(849)
评论(2) 编辑 收藏 引用