Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
 User ID: Password:
Register

## AC

Posted by 1019545352 at 2016-06-14 08:48:28 on Problem 2449
```#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<cmath>
#include<cstring>

using namespace std;

const int maxedge=2200000;
const int maxnode=2100000;
int nodecount,edgecount,s,t,k;
int dis[maxnode],from[maxnode],to[maxnode],val[maxnode];
/////////////////////图信息
struct edgenode{
int to,dis,next;
}e[maxedge];
int head[maxnode],tot;
void edge(int u,int v,int w)
{
e[++tot].to=v;
e[tot].dis=w;
e[tot].next=head[u];
head[u]=tot;
}
///////////////邻接表
struct Node{
int num,dist;
int g,h;
Node(int x,int y){
num=x;dist=y;
}
Node(int x,int y,int z){
num=x,g=y,h=z;
dist=g+h;
}
bool operator < (const Node &x)const{
return dist>x.dist;
}
};
void dijkstra(int s)
{
priority_queue<Node> que;
memset(dis,127/3,sizeof(dis));
dis[s]=0;
que.push(Node(s,0));
while(!que.empty()){
Node node=que.top();que.pop();
s=node.num;
if(node.dist != dis[s]) continue;
int x=head[s];
while(x!=0){
int to=e[x].to;
if(dis[to]> dis[s]+e[x].dis){
dis[to]=dis[s]+e[x].dis;
que.push(Node(to,dis[to]));
}
x=e[x].next;
}
}
}
////////////////dijkstra
void clear()
{
memset(head,0,sizeof(head));
memset(e,0,sizeof(e));
//for(int i=1;i<=tot;i++){
//	cout<<e[i].next<<e[i].dis<<e[i].to;
//	}
tot=0;
}
void secondedge()
{
for(int i=1;i<=edgecount;i++)
edge(from[i],to[i],val[i]);
}
int Astar(int s,int t,int k)
{
if(s==t) k++;
dijkstra(t);
priority_queue<Node>q;
clear();
secondedge();
q.push(Node(s,0,dis[s]));
while(!q.empty()){
Node x=q.top();q.pop();
if(x.num==t){
k--;
if(k==0){
return x.g;
}
}
int xx=head[x.num];
while(xx!=0){
q.push(Node( e[xx].to , x.g+e[xx].dis , dis[e[xx].to] ));
xx=e[xx].next;
}
}
return -1;
}
///////////////////Astar
int main()
{
//freopen("cowjog.in","r",stdin);
// freopen("cowjog.out","w",stdout);
scanf("%d%d",&nodecount,&edgecount);
for(int i=1;i<=edgecount;i++){
scanf("%d%d%d",&from[i],&to[i],&val[i]);
edge(to[i],from[i],val[i]);
}
scanf("%d%d%d",&s,&t,&k);
printf("%d",Astar(s,t,k));
return 0;
}```

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator