POJ——T 3225 Roadblocks
时间：2021-07-01 10:21:17
帮助过：14人阅读
#include <algorithm>
2 #include <cstdio>
3 #include <queue>
4
5 using namespace std;
6
7 const int INF(
0x3f3f3f3f);
8 const int N(
50000+
15);
9 const int M(
100000+
5);
10
11 int hed[N],had[N],sumedge;
12 struct Edge
13 {
14 int v,next,w;
15 }edge1[M],edge2[M];
16 inline
void ins(
int u,
int v,
int w)
17 {
18 edge1[++sumedge].v=
v;
19 edge1[sumedge].next=
hed[u];
20 edge1[sumedge].w=
w;
21 hed[u]=
sumedge;
22 edge2[sumedge].v=
u;
23 edge2[sumedge].next=
had[v];
24 edge2[sumedge].w=
w;
25 had[v]=
sumedge;
26 }
27
28 int dis[N];
29 bool inq[N];
30 void SPFA(
int s)
31 {
32 for(
int i=
1;i<s;i++) dis[i]=
INF;
33 dis[s]=
0; inq[s]=
1;
34 queue<
int>
que; que.push(s);
35 for(
int u,v;!
que.empty();)
36 {
37 u=que.front(); que.pop(); inq[u]=
0;
38 for(
int i=had[u];i;i=
edge2[i].next)
39 {
40 v=
edge2[i].v;
41 if(dis[v]>dis[u]+
edge2[i].w)
42 {
43 dis[v]=dis[u]+
edge2[i].w;
44 if(!inq[v]) que.push(v),inq[v]=
1;
45 }
46 }
47 }
48 }
49
50 struct Node
51 {
52 int now,g;
53 friend
bool operator <
(Node a,Node b)
54 {
55 return a.g+dis[a.now]>b.g+
dis[b.now];
56 }
57 };
58 int Astar(
int s,
int t,
int k)
59 {
60 priority_queue<Node>
que;
61 int cnt=
0; Node u,v;
62 u.g=
0; u.now=
s;
63 que.push(u);
64 for(;!
que.empty();)
65 {
66 u=
que.top(); que.pop();
67 if(u.now==t) cnt++
;
68 if(cnt==k)
return u.g;
69 for(
int i=hed[u.now];i;i=
edge1[i].next)
70 {
71 v.now=
edge1[i].v;
72 v.g=u.g+
edge1[i].w;
73 que.push(v);
74 }
75 }
76 }
77
78 inline
void read(
int &
x)
79 {
80 x=
0; register
char ch=
getchar();
81 for(;ch>
‘9‘||ch<
‘0‘;) ch=
getchar();
82 for(;ch>=
‘0‘&&ch<=
‘9‘;ch=getchar()) x=x*
10+ch-
‘0‘;
83 }
84
85 int AC()
86 {
87 int n,m; read(n),read(m);
88 for(
int v,u,w;m--
;)
89 read(u),read(v),read(w),ins(u,v,w);
90 SPFA(n); printf(
"%d\n",Astar(
1,n,
2));
91 return 0;
92 }
93
94 int I_want_AC=
AC();
95 int main(){;}
WA掉的A*
POJ——T 3225 Roadblocks
标签：search int hose moved include return 技术分享 link pre
