問題#
（翻訳が難しいので英語で記述）
Farmer John は最近オンラインで新しい車を購入しましたが、急いでいたため、車の追加機能を選択する際に「送信」ボタンを 2 回クリックしてしまいました。その結果、車には 2 つの GPS ナビゲーションシステムが装備されることになりました！さらに悪いことに、2 つのシステムは 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）を結びます。同じ組み合わせの交差点を複数の道路が結ぶことがあり、双方向の道路（両方向の通行が可能な道路）は、逆の向きに 2 つの別々の方向付き道路で表されます。FJ の家は交差点 1 にあり、彼の農場は交差点 N にあります。一連の方向付き道路を通って彼の家から農場に到達することができます。
両方の GPS ユニットは、上記で説明したとおり、同じ基本地図を使用しています。ただし、各道路の所要時間については異なる考え方を持っています。道路 i は、最初の GPS ユニットによると P_i 単位の時間がかかり、2 番目のユニットによると Q_i 単位の時間がかかります（各所要時間は 1 から 100,000 の範囲の整数です）。
FJ は家から農場まで旅行したいと思っています。ただし、FJ が道路をたどるたびに、GPS ユニットは FJ が X から Y への道路（たとえば、交差点 X から交差点 Y へ）を最短経路の一部ではないと信じている場合、大声でクレームを言います（FJ がどちらのユニットも好まない道路を通る場合、両方の GPS ユニットがクレームを言う可能性もあります）。
FJ が適切な経路を選択した場合、彼が受け取る可能性のある最小のクレームの合計数を求めてください。FJ が道路をたどるときに両方の GPS ユニットがクレームを言う場合、これは合計に + 2 としてカウントされます。
入力形式：
- 1 行目：整数 N と M。
i 行目は 4 つの整数で道路 i を説明します：A_i B_i P_i Q_i。
出力形式：
- 1 行目：FJ が自宅から農場まで最適な経路を選択した場合に受け取ることができる最小のクレームの合計数。
思考プロセス#
gps1 と gps2 の 2 つの逆グラフを作成し、それによって各点から n までの最短経路と各点の最短経路上の次の道路を求めることができます。そして、fj のためにグラフを作成し、各辺の初期重みを 2 とし、最短経路を求める際に次の道路がどの gps と一致するかによって重みを減らします。
コード#
#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;
}