水题笔记_ USACO14OPEN Dueling GPS's [最短路]

一遍不行就两遍

口胡得来终觉浅, 觉知此题要写明

懵逼的 题目

传送至 luogu

扯淡的 题解

emmmm偶然翻luogu发现的学长给我的题…然后就毫不犹豫的做啦…
大体思路就是从终点两遍最短路, 标记最短路

然后对每一条边

  • 有一个GPS以它为最短路的一部分时 设其边权为1
  • 有两个GPS以它为最短路的一部分时 设其边权为0
  • 没有GPS以它为最短路的一部分时 设边权为2

然后再(从起点)跑一边最短路… dis[n] 就是答案…

然后因为已经有了思路就写的飞快…30min左右写完惹(梦回巅峰!)…
然后没过样例
调了30min+…手玩了一遍样例…发现…诶诶诶样例怎么是错的啊…???
回去看看题目…发现翻译没有翻译出来 directional roads 所以这是个有向图啊喂!
然后…机房就快锁门惹…
第二天…交上去…T飞辣… 50…
发现是不是这题卡SPFA啊…
改成dijk…交上去T惹一个点…然后各种卡时…无果
发现标记某条边是否是最短路的一部分时写的非常诡异…可能被卡成 o(n ^ 2)
改完交上去…终于过惹…

我是不是傻啊QAQ

沙茶的 代码

诶诶诶写代码的时候脑子抽惹…写了三遍建图 + 最短路…
有空按照高级点的写法重写一遍

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
// T1.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#define MAXN (10000 + 5)
#define MAXM (50000 + 5)
#define INF (0x7ffffff)
const int s = 1;
int t = 1;
using namespace std;

struct edg
{
int from;
int to;
int next;
int cost;
bool atp;
bool atq;
}bp[MAXM << 1], bq[MAXM << 1], ba[MAXM << 1];
int cntp = 0, cntq = 0, cnta = 0;
int gp[MAXN], gq[MAXN], ga[MAXN];

int n;
int m;
int disp[MAXN], disq[MAXN], disa[MAXN];

struct cmpp
{
bool operator () (int x, int y)
{
return disp[x] > disp[y];
}
};

struct cmpq
{
bool operator () (int x, int y)
{
return disq[x] > disq[y];
}
};

struct cmpa
{
bool operator () (int x, int y)
{
return disa[x] > disa[y];
}
};

void init();
void inita();
void adnp(int, int, int);
void adnq(int, int, int);
void adna(int, int, int);

void dijkp(const int);
void dijkq(const int);
void dijka(const int);

int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
init();
dijkp(n);
dijkq(n);
inita();
dijka(1);
cout << disa[n];
return 0;
}

void init()
{
memset(disp, 0x7f, sizeof(disp));
memset(disq, 0x7f, sizeof(disq));
memset(disa, 0x7f, sizeof(disa));
cin >> n >> m;
t = n;
int srx, sry, srzp, srzq;
for (int i = 1; i <= m; i++)
{
cin >> srx >> sry >> srzp >> srzq;
//adnp(srx, sry, srzp);
adnp(sry, srx, srzp);
//adnq(srx, sry, srzq);
adnq(sry, srx, srzq);
adna(srx, sry, 2);
//adna(sry, srx, 2);
}
}

void dijkp(const int startDash)// 反向最短路: GPSp's way
{
bool v[MAXN];
int pre[MAXN];
memset(v, false, sizeof(v));
memset(pre, 0, sizeof(pre));
bp[0].from = startDash;
priority_queue<int, vector<int>, cmpp> q;
v[startDash] = true;
disp[startDash] = 0;
q.push(startDash);
while (!q.empty())
{
int dq = q.top(); q.pop();
v[dq] = true;
for (int i = gp[dq]; i; i = bp[i].next)
{
if (disp[bp[i].to] > disp[dq] + bp[i].cost)
{
disp[bp[i].to] = disp[dq] + bp[i].cost;
pre[bp[i].to] = i;
if (!v[bp[i].to])
q.push(bp[i].to);
}
}
}
}

void dijkq(const int startDash)// 反向最短路: GPSq's way
{
bool v[MAXN];
int pre[MAXN];
memset(v, false, sizeof(v));
memset(pre, 0, sizeof(pre));
bq[0].from = startDash;
priority_queue<int, vector<int>, cmpq> q;
v[startDash] = true;
disq[startDash] = 0;
q.push(startDash);
while (!q.empty())
{
int dq = q.top(); q.pop();
v[dq] = true;
for (int i = gq[dq]; i; i = bq[i].next)
{
if (disq[bq[i].to] > disq[dq] + bq[i].cost)
{
disq[bq[i].to] = disq[dq] + bq[i].cost;
pre[bq[i].to] = i;
if (!v[bq[i].to])
q.push(bq[i].to);
}
}
}
}

void dijka(const int startDash)// 正向最短路: ans
{
bool v[MAXN];
int pre[MAXN];
memset(v, false, sizeof(v));
priority_queue<int, vector<int>, cmpa> q;
v[startDash] = true;
disa[startDash] = 0;
q.push(startDash);
while (!q.empty())
{
int dq = q.top(); q.pop();
v[dq] = true;
for (int i = ga[dq]; i; i = ba[i].next)
{
if (disa[ba[i].to] > disa[dq] + ba[i].cost)
{
disa[ba[i].to] = disa[dq] + ba[i].cost;
pre[ba[i].to] = i;
if (!v[ba[i].to])
q.push(ba[i].to);
}
}
}
}


void adnp(int from, int to, int cost)
{
bp[++cntp].next = gp[from];
bp[cntp].from = from;
bp[cntp].to = to;
bp[cntp].cost = cost;
gp[from] = cntp;
}

void adnq(int from, int to, int cost)
{
bq[++cntq].next = gq[from];
bq[cntq].from = from;
bq[cntq].to = to;
bq[cntq].cost = cost;
gq[from] = cntq;
}

void adna(int from, int to, int cost)
{
ba[++cnta].next = ga[from];
ba[cnta].from = from;
ba[cnta].to = to;
ba[cnta].cost = cost;
ba[cnta].atp = false;
ba[cnta].atp = false;
ga[from] = cnta;
}

void inita()
{
bool v[MAXN];
queue<int> q;

memset(v, false, sizeof(v));
q.push(t);

while (!q.empty())// GPS p
{
int dq = q.front(); q.pop();
v[dq] = true;
for (int i = gp[dq]; i; i = bp[i].next)
{
if (disp[dq] + bp[i].cost == disp[bp[i].to] && !v[bp[i].to])
{
ba[i].atp = true;
q.push(bp[i].to);
}
}
}

memset(v, false, sizeof(v));
q.push(t);

while (!q.empty())// GPS q
{
int dq = q.front(); q.pop();
v[dq] = true;
for (int i = gq[dq]; i; i = bq[i].next)
{
if (disq[dq] + bq[i].cost == disq[bq[i].to] && !v[bq[i].to])
{
ba[i].atq = true;
q.push(bq[i].to);
}
}
}

for (int i = 1; i <= m; i++)
{
if (ba[i].atp)
ba[i].cost--;
if (ba[i].atq)
ba[i].cost--;
}
}

/*
5 7
3 4 7 1
1 3 2 20
1 4 17 18
4 5 25 3
1 2 10 1
3 5 4 14
2 4 6 5
*/

By 文化课爆炸的 Cansult