Bzoj 3445(最短路+枚举)

bzoj 3445
Luogu免权限地址
先对原图进行一次最短路,然后记录最短路上的边,然后枚举每一条边加倍,进行最短路,取每次最短路的答案减去原图最短路即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define ms(i,j) memset(i,j, sizeof i);
using namespace std;
const int MAXN = 100 + 10, INF = 100000000;
struct node
{
int dis, no;
bool operator < (const node &b) const {return dis>b.dis;}
};
struct edge
{
int u,v;
}E[5000+100];
int cnt = 0;
int G[MAXN][MAXN];
int dis[MAXN];
int vi[MAXN];
int pre[MAXN];
int n,m;
int ans = 0, oa;
void fdij()
{
priority_queue<node> pq;
for (int i=1;i<=n;i++) dis[i] = INF, vi[i] = false, pre[i] = 0; dis[1] = 0;
pq.push((node){0, 1});
while (!pq.empty())
{
node p = pq.top(); pq.pop();
if (vi[p.no]) continue;
vi[p.no] = true;
for (int i=1;i<=n;i++)
if (G[i][p.no]!=INF)
if (dis[p.no]+G[p.no][i]<dis[i])
{
dis[i] = dis[p.no]+G[p.no][i];
pre[i] = p.no;
pq.push((node){dis[i], i});
}
}
oa = ans = dis[n];
}
void dij()
{
priority_queue<node> pq;
for (int i=1;i<=n;i++) dis[i] = INF, vi[i] = false; dis[1] = 0;
pq.push((node){0, 1});
while (!pq.empty())
{
node p = pq.top(); pq.pop();
if (vi[p.no]) continue;
vi[p.no] = true;
for (int i=1;i<=n;i++)
if (G[i][p.no]!=INF)
if (dis[p.no]+G[p.no][i]<dis[i])
{
dis[i] = dis[p.no]+G[p.no][i];
pq.push((node){dis[i], i});
}
}
ans = max(ans, dis[n]);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++) G[i][j] = INF;
for (int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d", &x, &y, &z);
G[x][y] = G[y][x] = z;
}
fdij();
int now = n;
while (pre[now]!=0)
{
E[++cnt].u = now;
E[ cnt].v = pre[now];
now = pre[now];
}
for (int i=1;i<=cnt;i++)
{
int x = E[i].u;
int y = E[i].v;
G[x][y] *= 2;
G[y][x] *= 2;
dij();
G[x][y] /= 2;
G[y][x] /= 2;
}
printf("%d\n", ans-oa);
return 0;
}

------ 本文结束 ------