[USACO14FEB]路障Roadblock
时间：2021-07-01 10:21:17
帮助过：49人阅读
#include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #define M 15000
5 #include<queue>
6 #define N 110
7 using namespace std;
8 int n,m;
9 int po,ans;
10 int head[N],to[M],next[M],len[M],e=
1;
11 void buid(
int u,
int v,
int l)
12 {
13 next[++e]=head[u],head[u]=
e;
14 to[e]=v,len[e]=
l;
15 }
16 int dis[N],init[N];
17 int pre[N],fr[N],that[M],nu;
18 queue<
int>
q;
19 void spfa(
int s)
20 {
21 memset(dis,
20,
sizeof(dis));
22 dis[s]=
0;init[s]=
1,q.push(s);
23 while(!
q.empty())
24 {
25 int now=q.front();q.pop();init[now]=
0;
26 for(
int i=head[now];i;i=
next[i])
27 {
28 int j=
to[i];
29 if(dis[j]>dis[now]+
len[i])
30 {
31 dis[j]=dis[now]+
len[i];
32 pre[j]=i;fr[j]=
now;
33 if(!
init[j])
34 {
35 init[j]=
1;q.push(j);
36 }
37 }
38 }
39 }
40 }
41 int main()
42 {
43 scanf(
"%d%d",&n,&
m);
44 for(
int i=
1;i<=m;++
i)
45 {
46 int u,v,l;
47 scanf(
"%d%d%d",&u,&v,&
l);
48 buid(u,v,l);
49 buid(v,u,l);
50 }
51 spfa(
1);po=
dis[n];
52 int now=
n;
53 while(now!=
1)
54 {
55 that[++nu]=pre[now];
//记路径
56 now=
fr[now];
57 }
58 for(
int i=
1;i<=nu;++i)
//枚举路径
59 {
60 len[that[i]]*=
2;
61 len[that[i]^
1]*=
2;
62 spfa(
1);
//操♂作
63 ans=
max(ans,dis[n]);
64 len[that[i]]/=
2;
65 len[that[i]^
1]/=
2;
66 }
67 cout<<ans-po<<endl;
//end
68 return 0;
69 }
[USACO14FEB]路障Roadblock
标签：class lock 设计 init ios input RKE return 解题思路
