题目#
（翻译太水了所以用英文）
Farmer John 最近在线购买了一辆新车，但由于匆忙，他在选择额外功能时不小心点击了 “提交” 按钮两次，结果这辆车配备了两个 GPS 导航系统！更糟糕的是，这两个系统经常对 FJ 应该选择的路线做出相互冲突的决定。
FJ 所在地区的地图由 N 个交叉口 (2 <= N <= 10,000) 和 M 条单向道路 (1 <= M <= 50,000) 组成。道路 i 连接交叉口 A_i (1 <= A_i <= N) 和 B_i (1 <= B_i <= N)。多条道路可以连接同一对交叉口，双向道路 (允许双向通行) 由两个方向相反的单向道路表示。FJ 的家位于交叉口 1，他的农场位于交叉口 N。可以通过沿着一系列单向道路从他的家到达农场。
两个 GPS 单元使用的底层地图如上所述；然而，它们对每条道路的行驶时间有不同的看法。根据第一个 GPS 单元，道路 i 需要 P_i 单位时间通过，而根据第二个单元则需要 Q_i 单位时间通过 (每个行驶时间都是 1..100,000 范围内的整数)。
FJ 想要从他的家前往农场。然而，每当 FJ 跟随一条道路 (比如，从交叉口 X 到交叉口 Y) 时，GPS 单元都会大声抱怨，认为这条道路不是从 X 到农场的最短路线的一部分 (如果 FJ 走了一条两个 GPS 单元都不喜欢的道路，可能会导致两个 GPS 单元同时抱怨)。
请帮助 FJ 确定如果他选择合适的路线，能够收到的最少投诉总数。如果两个 GPS 单元在 FJ 跟随一条道路时都抱怨，这将计为 +2。
输入格式：
- 第 1 行：整数 N 和 M。
第 i 行描述道路 i，包含四个整数：A_i B_i P_i Q_i。
输出格式：
- 第 1 行：如果 FJ 从他的家到农场的路线最优，他能够收到的最少投诉总数。
思路#
分别为 gps1 和 gps2 建两个反图，这样就可以 spfa 求出每个点到 n 的最短路和每个点的最短路上的下一条边。然后为 FJ 建一个图，每条边的初始权值为 2，表示警告次数，在求最短路时如果下一条边与某个 GPS 相同，警告次数就减一。
Code#
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int MAXN = 10000 + 5;
int n, m;
struct mp {
struct ed {
int to, w, nex;
} e[MAXN * 6];
int newp;
int head[MAXN], fa[MAXN], d[MAXN];
bool inq[MAXN];
void lineAdd (int p1, int p2, int w) {
++newp;
e[newp].to = p2;
e[newp].w = w;
e[newp].nex = head[p1];
head[p1] = newp;
}
void spfa (int s) {
memset(inq, 0, sizeof(inq));
memset(d, 0x3f, sizeof(d));
queue<int> q;
q.push(s);
d[s] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
inq[u] = 0;
for (int i = head[u]; i; i = e[i].nex) {
int y = e[i].to;
if (d[u] + (e[i].w) < d[y]) {
d[y] = d[u] + e[i].w;
fa[y] = i;
if (!inq[y]) {
q.push(y);
inq[y] = 1;
}
}
}
}
}
};
mp g1, g2, fj;
void spfa_for_fj(void) {
memset(fj.inq, 0, sizeof(fj.inq));
memset(fj.d, 0x3f, sizeof(fj.d));
queue<int> q;
q.push(1);
fj.d[1] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
fj.inq[u] = 0;
for (int i = fj.head[u]; i; i = fj.e[i].nex) {
int y = fj.e[i].to, w = fj.e[i].w;
if (g1.fa[u] == i) --w;
if (g2.fa[u] == i) --w;
if (fj.d[u] + w < fj.d[y]) {
fj.d[y] = fj.d[u] + w;
if (!fj.inq[y]) {
q.push(y);
fj.inq[y] = 1;
}
}
}
}
}
int main (void) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
int p1, p2, w1, w2;
scanf("%d%d%d%d", &p1, &p2, &w1, &w2);
g1.lineAdd(p2, p1, w1);
g2.lineAdd(p2, p1, w2);
fj.lineAdd(p1, p2, 2);
}
g1.spfa(n);
g2.spfa(n);
spfa_for_fj();
printf("%d\n", fj.d[n]);
fclose(stdin);
fclose(stdout);
return 0;
}