#include <algorithm>
2 #include <cstdio>
3 #include <queue>
4
5 using namespace std;
6
7 const int INF(
0x3f3f3f3f);
8 const int N(
5000+
105);
9 const int M(
200000+
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 edge1[++sumedge].v=
u;
28 edge1[sumedge].next=
hed[v];
29 edge1[sumedge].w=
w;
30 hed[v]=
sumedge;
31 edge2[sumedge].v=
v;
32 edge2[sumedge].next=
had[u];
33 edge2[sumedge].w=
w;
34 had[u]=
sumedge;
35 }
36
37 int dis[N];
38 bool inq[N];
39 void SPFA(
int s)
40 {
41 for(
int i=
1;i<s;i++) dis[i]=
INF;
42 dis[s]=
0; inq[s]=
1;
43 queue<
int>
que; que.push(s);
44 for(
int u,v;!
que.empty();)
45 {
46 u=que.front(); que.pop(); inq[u]=
0;
47 for(
int i=had[u];i;i=
edge2[i].next)
48 {
49 v=
edge2[i].v;
50 if(dis[v]>dis[u]+
edge2[i].w)
51 {
52 dis[v]=dis[u]+
edge2[i].w;
53 if(!inq[v]) que.push(v),inq[v]=
1;
54 }
55 }
56 }
57 }
58
59 struct Node
60 {
61 int now,g;
62 bool operator < (Node a)
const
63 {
64 return a.g+dis[a.now]<g+
dis[now];
65 }
66 };
67 int Astar(
int s,
int t,
int k)
68 {
69 priority_queue<Node>
que;
70 int cnt=
0; Node u,v;
71 u.g=
0; u.now=
s;
72 que.push(u);
73 for(;!
que.empty();)
74 {
75 u=
que.top(); que.pop();
76 if(u.now==t) cnt++
;
77 if(cnt==k)
return u.g;
78 for(
int i=hed[u.now];i;i=
edge1[i].next)
79 {
80 v.now=
edge1[i].v;
81 v.g=u.g+
edge1[i].w;
82 que.push(v);
83 }
84 }
85 return 0;
86 }
87
88 inline
void read(
int &
x)
89 {
90 x=
0; register
char ch=
getchar();
91 for(;ch>
‘9‘||ch<
‘0‘;) ch=
getchar();
92 for(;ch>=
‘0‘&&ch<=
‘9‘;ch=getchar()) x=x*
10+ch-
‘0‘;
93 }
94
95 int AC()
96 {
97 // freopen("block.in","r",stdin);
98 // freopen("block.out","w",stdout);
99
100 int n,m; read(n),read(m);
101 for(
int v,u,w;m--
;)
102 read(u),read(v),read(w),ins(u,v,w);
103 SPFA(n); printf(
"%d\n",Astar(
1,n,
2));
104 return 0;
105 }
106
107 int I_want_AC=
AC();
108 int main(){;}
Astar AC
次短路正经做法：
SPFA跑出从1到i和从n到i的dis，枚举每条不在最短路上的边，更新ans
1 #include <algorithm>
2 #include <cstdio>
3 #include <queue>
4
5 using namespace std;
6
7 const int INF(0x3f3f3f3f);
8 const int N(5000+105);
9 const int M(100000+5);
10
11 int m,n,head[N],sumedge;
12 struct Edge
13 {
14 int v,next,w;
15 Edge(int v=0,int next=0,int w=0):
16 v(v),next(next),w(w){}
17 }edge[M<<1];
18 inline void ins(int u,int v,int w)
19 {
20 edge[++sumedge]=Edge(v,head[u],w);
21 head[u]=sumedge;
22 }
23
24 bool inq[N];
25 int d1[N],d2[N];
26 inline void SPFA(int s,int *dis)
27 {
28 for(int i=1;i<=n;i++)
29 inq[i]=0,dis[i]=INF;
30 dis[s]=0; inq[s]=1;
31 queue<int>que; que.push(s);
32 for(int u,v;!que.empty();)
33 {
34 u=que.front(); que.pop(); inq[u]=0;
35 for(int i=head[u];i;i=edge[i].next)
36 {
37 v=edge[i].v;
38 if(dis[v]>dis[u]+edge[i].w)
39 {
40 dis[v]=dis[u]+edge[i].w;
41 if(!inq[v]) que.push(v),inq[v]=1;
42 }
43 }
44 }
45 }
46
47 inline void read(int &x)
48 {
49 x=0; register char ch=getchar();
50 for(;ch>‘9‘||ch<‘0‘;) ch=getchar();
51 for(;ch>=‘0‘&&ch<=‘9‘;ch=getchar()) x=x*10+ch-‘0‘;
52 }
53
54 int AC()
55 {
56 freopen("block.in","r",stdin);
57 freopen("block.out","w",stdout);
58
59 read(n),read(m);
60 for(int v,u,w;m--;ins(u,v,w),ins(v,u,w))
61 read(u),read(v),read(w);
62 SPFA(1,d1); SPFA(n,d2);
63 int ans=INF,tmp;
64 for(int i,v,u=1;u<=n;u++)
65 {
66 for(int i=head[u];i;i=edge[i].next)
67 {
68 v=edge[i].v;
69 tmp=d1[u]+d2[v]+edge[i].w;
70 if(tmp>d1[n]&&ans>tmp) ans=tmp;
71 }
72 }
73 printf("%d\n",ans);
74 return 0;
75 }
76
77 int I_want_AC=AC();
78 int main(){;}
SPFA 跑次短路
POJ——T 3255 Roadblocks|| COGS——T 315. [POJ3255] 地砖RoadBlocks || 洛谷—— P2865 [USACO06NOV]路障Roadblocks
标签：stdout nod const section targe block nat open input
