http://poj.org/problem?id=2449
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=1e3+; /**
求第K短的算法基于BFS搜索，当终点出队K次时，所走的总距离就是第K短路，
不过这样那些不该走的路会被反复的走，造成许多空间时间浪费，这时候就要用到启发式的A*搜索
**/ ///from s to t
///opp:from t to s struct node
{
int d,len;
node *next;
}*e[maxn],*oppe[maxn]; ///h:from this point to destination(predict must:predict<actual)
///g:from source to this point(actual)
int h[maxn],unreach; struct rec
{
int d,dist;
bool operator<(const rec &b) const
{
return b.dist<dist;
}
};
priority_queue<rec>st; struct noa
{
int d,dist,pre;
bool operator<(const noa &b) const
{
if (b.pre==pre)
return b.dist<dist;
return b.pre<pre;
}
};
priority_queue<noa>ast; bool vis[maxn];
int s,t,ind,ci[maxn]; int astar()
{
int d,dist;
node *p;
///多组数据时需要
// while (!ast.empty())
// ast.pop();
if (h[s]!=unreach)
ast.push({s,,h[s]});
while (!ast.empty())
{
d=ast.top().d;
dist=ast.top().dist;
ast.pop();///!
ci[d]++;
if (ci[d]==ind && d==t)
return dist;///而不是ast.top().dist
///优化
if (ci[d]>ind)
continue; p=e[d];
while (p)
{
if (h[p->d]!=unreach)
///aster
ast.push({p->d,dist+p->len,dist+p->len+h[p->d]});
///just dijkstra
// ast.push({p->d,dist+p->len,dist+p->len});
p=p->next;
}
}
return -;
} void opp_dijkstra()
{
int d,dd;
node *p;
memset(h,0x7f,sizeof(h));
unreach=h[];
h[t]=;
st.push({t,});
while ()
{
while (!st.empty() && vis[st.top().d])
st.pop();
if (st.empty())
break;
d=st.top().d;
st.pop();
vis[d]=;
p=oppe[d];///
while (p)
{
dd=p->d;
if (h[dd]>h[d]+p->len)
{
h[dd]=h[d]+p->len;
st.push({dd,h[dd]});
}
p=p->next;
}
}
} int main()
{
int a,b,c,n,m,i;
node *p;
scanf("%d%d",&n,&m);
for (i=;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
p=new node();
p->d=b;
p->len=c;
p->next=e[a];
e[a]=p; p=new node();
p->d=a;
p->len=c;
p->next=oppe[b];
oppe[b]=p;
}
scanf("%d%d%d",&s,&t,&ind);
///!!!
if (s==t)
ind++;
// ///shortest path
// scanf("%d%d",&s,&t);
// ind=1;
opp_dijkstra();
printf("%d",astar());
return ;
}
/*
2 2
1 2 1
2 1 1
1 1 1 3 3
1 2 1
2 3 2
3 2 1
1 1 1 3 3
1 2 1
2 3 2
3 1 3
1 1 2 3 1
1 2 3
1 3 1 3 2
1 2 10
2 3 2
1 3 1 3 2
1 2 10
2 3 2
1 3 2 4 4
1 3 2
3 2 5
1 4 3
4 2 1
1 2 2 x
4 4
1 2 100000
2 3 1
3 2 1
3 4 100000
1 4 1000 3 4
1 2 1
2 1 2
2 3 1
3 2 1
2 3 5 3 3
1 2 1000
1 3 1
3 2 1
1 2 1 */
https://www.luogu.org/problemnew/show/P2483
68分……
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=5e3+; struct node
{
int d;
double len;
node *next;
}*e[maxn],*oppe[maxn]; ///h:from this point to destination(predict must:predict<actual)
///g:from source to this point(actual)
double h[maxn],unreach;
double tot; struct rec
{
int d;
double dist;
bool operator<(const rec &b) const
{
return b.dist<dist;
}
};
priority_queue<rec>st; struct noa
{
int d,g;
double dist,pre;
bool operator<(const noa &b) const
{
if (b.pre==pre)
return b.dist<dist;
return b.pre<pre;
}
};
priority_queue<noa>ast; bool vis[maxn];
int s,t,ind,re,n,m;
int ci[maxn]; void aster()
{
int d,dd,g;
double dist,ddist;
node *p;
ind=tot/h[];///限制次数 if (h[s]!=unreach)
ast.push({s,,,h[s]});
while (!ast.empty())
{
d=ast.top().d;
dist=ast.top().dist;
g=ast.top().g;
ast.pop();///!
ci[d]++;
if (d==t)
{
if (dist>tot)
return;
tot-=dist;
re++;
ind=re+tot/dist;///限制次数，优化
continue; ///这题的坑爹地方：到达终点，就不能再走了
} p=e[d];
while (p)
{
dd=p->d;
ddist=dist+p->len;
if (h[dd]!=unreach && g!=m && ci[dd]<ind && ddist<=tot)
ast.push({dd,g+,ddist,ddist+h[p->d]});
p=p->next;
}
}
} void opp_dijkstra()
{
int d,dd,i;
node *p;
unreach=1.0e11;
for (i=;i<=n;i++)
h[i]=unreach; h[t]=;
st.push({t,});
while ()
{
while (!st.empty() && vis[st.top().d])
st.pop();
if (st.empty())
break;
d=st.top().d;
st.pop();
vis[d]=;
p=oppe[d];///
while (p)
{
dd=p->d;
if (h[dd]>h[d]+p->len)
{
h[dd]=h[d]+p->len;
st.push({dd,h[dd]});
}
p=p->next;
}
}
} int main()
{
int a,b,i;
double c;
node *p,*pp;
scanf("%d%d",&n,&m);
scanf("%lf",&tot);
for (i=;i<=m;i++)
{
scanf("%d%d%lf",&a,&b,&c);
p=new node();
p->d=b;
p->len=c;
p->next=e[a];
e[a]=p; p=new node();
p->d=a;
p->len=c;
p->next=oppe[b];
oppe[b]=p;
}
s=,t=n;
opp_dijkstra();
///lower the memory
for (i=;i<=n;i++)
{
p=oppe[i];
while (p)
{
pp=p;
p=p->next;
free(pp);
}
}
aster();
printf("%d",re);
return ;
}