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

## AC ~~~~~~~~~~~~~~~~~~~~>>

Posted by ACAccepted at 2019-03-09 10:54:44 on Problem 2449
```#include <cstdio>
#include <queue>
using namespace std;

{
int x=0,f=1;char c=getchar();
while (c<'0' || c>'9'){if (c=='-')f=-1;c=getchar();}
while (c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
return x*f;
}

int print(int x)
{
if (x<0)x=-x,putchar('-');
if (x>9)print(x/10);
putchar(x%10+48);
}

int print(int x,char c)
{
print(x);
putchar(c);
}

const int INF=100000000;
const int MAXN=1010;
const int MAXM=100010;
int n,m,id[2],from,to,k;

struct edge
{
int v,w,nx;
}set[2][MAXM];
int dis[MAXN];
bool vis[MAXN];

struct dij
{
int id,dis;

bool operator < (const dij tmp) const
{
return dis>tmp.dis;
}
};

struct star
{
int id,f,g;

bool operator < (const star tmp) const
{
if (f==tmp.f)return g>tmp.g;
return f>tmp.f;
}
};

inline void Addedge(int cnt,int u,int v,int w)
{
}

inline void dijkstra(int s)
{
priority_queue<dij> Q;
for (int i=1;i<=n;i++)dis[i]=INF;
dis[s]=0;
Q.push((dij){s,0});
struct dij top;
int u,v,w;
while (!Q.empty())
{
u=Q.top().id;
Q.pop();
vis[u]=0;
{
v=set[1][k].v;w=set[1][k].w;
if (dis[u]+w<dis[v])
{
dis[v]=dis[u]+w;
if (!vis[v])
{
vis[v]=true;
Q.push((dij){v,dis[v]});
}
}
}
}
}

inline void init()
{
int u,v,w;
for (int i=1;i<=m;i++)
{
}
dijkstra(to);
}

inline int A_star(int cnt)
{
priority_queue<star> Q;
if (from==to)cnt++;
Q.push((star){from,0,0});
struct star top;
while (!Q.empty())
{
top=Q.top();Q.pop();
if (top.id==to)
if ((--cnt)==0)
Q.push((star){set[0][k].v,top.g+set[0][k].w+dis[set[0][k].v],top.g+set[0][k].w});
}
return -1;
}

int main()
{
init();
print(A_star(k));
return 0;
}```

Followed by: